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.

# 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:

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

## Visualizations https://visualgo.net/en https://www.toptal.com/developers/sorting-algorithms http://sorting.at/