CISC 3130 Data Structures: Sorting Algorithms

Logic:

1. Start at position i = 0
2. Compare two pair  i and i+1
3. If A[i] >  A[i+1], swap elements
4. Move pointer one position right.

BubbleSort( int a[])
    int out, in
    for out = a.length-1 to 1
        for in = 0 to out
            if a[in] > a[in+1]
                temp = a[in]
                a[in] = a[in+1]
                a[in+1] = temp
        end for
    end for

Logic:

1. Divide to find midpoint q. Split input array to [0..q] and [q + 1..n]
2. Conquer by recursively sorting subarrays from first step.
3. Combine by merging the two sorted sub arrays.

mergesort(A, n):   # Sort an array of size n
  mergesort(first half of A, n/2)
  mergesort(second half of A, n/2)
  merge(first half of A, second half of A)

merge (A):

while A not empty or B not empty:
  if first element of A < first element of B:
      remove first element from A
      insert element into C
  end if
  else:
      remove first element from B
      insert element into C
end while

Logic:
1. Start at position i = 0, find smallest element
2. Swap that with position 0
3. Repeat from position 1 to n, replace next smallest element with position 1 and so on
4. Keep repeating until reaching last position

SelectionSort(int a[])
    for i = 0 to a.length – 1
        min=i
        for j=i+1 to a.length - 1
            if a[j]<a[min]
                min=j
        end for
        swap a[i] and a[min]
    end for

Logic:

1. Choose the pivot, store in the rightmost element
2. Partition the array into left (smaller keys) and right (larger keys) groups
3. Call self to sort the left group
4. Call self to sort the right group

5. Merge groups

QuickSort(int a[])
    if start index < end index
        partition list around a pivot
        QuickSort (aLeft[])
        QuickSort (aRight[])

Logic:
1. Marked item is first unsorted
2. Move this element to temporary variable
3. Shift sorted elements until space opens for temporary variable, place in.
4. Repeat with next unsorted item

InsertionSort(int a[])
    int out, in
    for out = 1 to a.length – 1
        temp = a[out]
        in = out
        while in>0 and a[in-1]>=temp
            a[in] = a[in - 1]
            in--
        end while
        a[in] = temp
    end for

Logic:

1. Start with max heap
2. Remove root and put into last/vacant place
3. Reduce heap size by 1, heapify
4. Repeat
 

Heapsort(A) {
  BuildHeap(A)
  for i <- length(A) downto 1 {
      exchange A[0] <-> A[i]
      heapsize <- heapsize -1
      Heapify(A, 0)
}

Heapify(A, i) {
  le <- left(i),    ri <- right(i)
  if (le<=heapsize) and (A[le]>A[i])
      largest <- le
  else
      largest <- i
  if (ri<=heapsize) and (A[ri]>A[largest])
      largest <- ri
  if (largest != i) {
      exchange A[i] <-> A[largest]
      Heapify(A, largest)
  }
}