Sorting

SORTING

Sorting involves putting dat a in a specified order.
There are many ways of putti ng data in an array in order by value.
Bubble sort
Principle: For each item of the array, if the item is larger than its successor, swap the values. Continue this process until a complete pass through the array is made without a swap.
Algorithm
Input: array of values in random order
Output: array of values sorted in ascending order by value
begin
  Set sorted to false.
  while not sorted
    Set sorted to true.
    for i = first to next-to-last
      if value at i > value at i+1
        Swap value at i and value at i+1.
        Set sorted to false.
end
Selection sort (aka successive minima sort)
Principle: Find the least value in the remaining part of the array and put that value at the top.
Algorithm
Input: array of values in random order
Output: array of values sorted in ascending order by value
begin
  for i = first to next-to-last
    least = i;
    for j = i+1 to last
      if value at least > value at j
        least = j
    Swap value at i and value at least.
end
Quicksort
Principle: By dividing the part of the array under consideration in half, put smaller values to the left of the middle value and larger values to the right of the middle value. Continue this process until all parts of the array have been considered.
Algorithm
Input: array of values in random order, first index, last index
Output: array of values sorted in ascending order by value
begin
  Set left to first.
  Set right to last.
  Set pivot to value at (left + right) / 2.
  while left < right
    while value on left < pivot
      Increment left.
    while value on right > pivot
      Decrement right.
    if left <= right
      Swap value at left and value at right.
      Increment left.
      Decrement right.
    if first < right
      Quicksort part of array from first to right.
    if last > left
      Quicksort part of array from left to last.
end

C++ version

void quicksort (int a[], int first, int last) {
  int left = first, right = last, pivot = a[(first + right)/2];
  while (left <= right) {
    while (a[left] < pivot)
      left++;
    while (a[right] > pivot)
      right--;
    if (left <= right) {
      int temp = a[left];
      a[left] = a[right];
      a[right] = temp;
      left++;
      right--;
    }
  }
  if (right > first)
    quicksort (a, first, right);
  if (left < last)
    quicksort (a, left, last);
}
Comparing the above methods of sorting
Simplicity: bubble, selection
Data nearly sorted: bubble, quicksort
Run-time efficiency Based on number of elements in array
Bubble: n squared
Selection: n squared
Quicksort: n log n

 

 

Back Home Up