Heap Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting and a family member of the selection sort. As the name suggests, this sorting algorithm use the concept of a heap structure that is based on the binary tree, which works as follows:
1. Using an array and the given data items, build a heap i.e. either a min heap or max heap as per requested sorting order
2. From the heap, remove the root node's data items and insert it to an separate array
3. Wait until the heap orders is restored, which will produces a new root node. Now, recursively repeat the above procedure '2' until there is no data items left in the heap.
Click the link -> Heap Sort for the pseudocode
Showing posts with label Comparison Sort. Show all posts
Showing posts with label Comparison Sort. Show all posts
Tuesday, March 10, 2009
Monday, March 9, 2009
What is Quick Sort?
Quick Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting.
This algorithm works as follows:
1. Reorder by spiting the sequence into left and right halves with a pivot data item in between. Here, pivot data item is identified by comparison i.e. a data item must be greater than or equal to every data item in the left half & less than or equal to every data item in the right half.
2. Now, recursively sort the two half's separately.
This algorithm works as follows:
1. Reorder by spiting the sequence into left and right halves with a pivot data item in between. Here, pivot data item is identified by comparison i.e. a data item must be greater than or equal to every data item in the left half & less than or equal to every data item in the right half.
2. Now, recursively sort the two half's separately.
What is Merge Sort?
Merge sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting.
Here we apply the divide-and-conquer strategy to sort a given sequence of data items, which can be described as follows:
1. Recursively split the sequence into two halves (i.e. subsequences) until the subsequence contains only a single data item (i.e. singleton subsequence)
2. Now, recursively merge these subsequences back together preserving their required order (i.e. ascending or descending order)
Here we apply the divide-and-conquer strategy to sort a given sequence of data items, which can be described as follows:
1. Recursively split the sequence into two halves (i.e. subsequences) until the subsequence contains only a single data item (i.e. singleton subsequence)
2. Now, recursively merge these subsequences back together preserving their required order (i.e. ascending or descending order)
Friday, March 6, 2009
What is Selection Sort?
Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort.
Sorting takes place by stepping through all the data items one-by-one while looking for either largest or smallest data item and making only one swap after finding either largest or smallest data item. Hence, this sorting algorithm is referred to as the selection sort because on each pass this algorithm selects either largest or smallest of the remaining unsorted data items and places them in the right order.
click the link -> Selection Sort for the pseudocode
Sorting takes place by stepping through all the data items one-by-one while looking for either largest or smallest data item and making only one swap after finding either largest or smallest data item. Hence, this sorting algorithm is referred to as the selection sort because on each pass this algorithm selects either largest or smallest of the remaining unsorted data items and places them in the right order.
click the link -> Selection Sort for the pseudocode
Subscribe to:
Posts (Atom)