Skip to Main Content
It looks like you're using Internet Explorer 11 or older. This website works best with modern browsers such as the latest versions of Chrome, Firefox, Safari, and Edge. If you continue with this browser, you may see unexpected results.
| Brooklyn College Library & Academic IT |CISC Department

CISC 3130 Data Structures: Sorting Algorithms

Professor Chuang Spring 2020 OER

Introduction

Sorting algorithms perform the operation of turning a collection of elements into ascending order, where items are arranged from smallest value to largest value. 

Overview

  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Quicksort
  • Mergesort
  • Shellsort
  • Heap Sort

Bubble Sort

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

 

Mergesort

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

 

 

 

 

Selection Sort

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

 

Quicksort

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[])

 

 

 

 

 

Insertion Sort

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

 

Heapsort

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)
  }
}