## Quick Sort

Definition:

Quick Sort is an algorithm that sorts unsorted lists and arrays.

In worst case, time complexity of Quick Sort is O ( n^2). In average and best case, time complexity of that algorithm is  O (n logn).

It is divide and conquer algorithm and invented by Tony Hoare.

It is also in-place algorithm, so it doesn’t require extra space of memory. This property make this algorithm more popular in practice.

Properties of Quick Sort:

• Not Stable,
• O ( logn) extra space,
• Often faster algorithm than other O ( n logn) algoirthms in practice.
• In-place algorithm.

How does it work?

1.  Pick an element from array. This element is called Pivot.

2. Reorder the array according to pivot. Elements smaller than pivot come before pivot and elements bigger than pivot come after the pivot.  This operation is called partition.  Pivot gets its final position after partitioning.

3. Recursively do it again for subarrays of the list.

In the figure below, you can see the animated figure of this algorithm. Animated Figure of Quick Sort

In the example below, you can see pivot (4), partition algorithm and partioning in sub arrays. Quick Sort

Animation:

For better understanding, go to this animation page.

Pseudocode:

```QuickSort:
quicksort(A, i, k):
if i < k:
p := partition(A, i, k)
quicksort(A, i, p - 1)
quicksort(A, p + 1, k)

Partition:
// left is the index of the leftmost element of the subarray
// right is the index of the rightmost element of the subarray (inclusive)
// number of elements in subarray = right-left+1
partition(array, left, right)
pivotIndex := choose-pivot(array, left, right)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right]
storeIndex := left
for i from left to right - 1
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right]  // Move pivot to its final place
return storeIndex```

References:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (second ed.), MIT Press and McGraw-Hill,

Figures from:  http://en.wikipedia.org

## Bubble Sort

Definition:

Bubble sort is another type of sorting algorithm that sort unsorted lists and arrays.

In worst and  average case its time complexity is O(n^2) (n square). However, In best case, time complexity of this algorithm is O (n).

Properties of Bubble Sort:

• Stable,
• O(n^2) comparison and swap,
• O(1) memory space.

Its properties are mostly same as insertion sort.

How does it work?

In bubble sort,

1. It starts at the beginning of unsorted list and it compares every adjacent pair.

2. If the elements in the pair are not right position, swap them.

3. The largest (or smallest ) one goes to the at the end of the list.

4. This iteration goes on until list is getting sort.

Elements in the list move like bubbles in the water.  They move upward to reach surface of the water.

In the figure below, you can see the animated bubble sort example. Animated Bubble Sort Example

Another example for bubble sort: Bubble Sort Example

Animation:

For better understanding, go to this animation page.

Pseudocode:

```for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end```

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/

Figure from:  http://en.wikipedia.org

For more algorithms, go to Algorithms Section.

## Selection Sort

Definition:

Selection sort is a type of sort algorithm that sort the unsorted arrays.

In worst, average and best case its time complexity is O(n^2) (n square). It is inefficient in large data sets. However, it has simple implementation and it does not require extra memory.

Its properties:

• Not stable,
• O(n^2) time complexity,
• O (1) memory space,
• In-place comparison sort,
• O ( n) for swaps.

How does it work?

In selection sort, array is divided into 2 parts : sorted and unsorted list.

1. Firstly, sorted list is empty, unsorted list has entire input.
2. Find the smallest element in the unsorted list, and put it into sorted list.
3. After all, array is sorted.

Example:

```70  52  45  5   8  // initially
5  52  45  70  8 // sorted list= 5
5  8  45  70 52 // sorted list= 5 8
5  8  45 70 52  // sorted list= 5 8 45
5  8  45 52 70 // sorted list= 5 8 45 52
5  8 45 52 70 // sorted list=  5 8 45 52 70

```

A figure below shows the selection sort: Animated Selection Sort

Animation:

For better understanding, go to this animation page.

Pseudocode:

```for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
→ invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end```

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/

Figure from:  http://en.wikipedia.org

For more algorithms, go to Algorithms Section.

## Merge Sort

Definition:

Merge Sort is a type of sorting algorithm. It is a divide and conquer algorithm and  it was invented by John von Neumann.

In worst, average and best case its time complexity is O(n logn).

Its Properties in short:

• Stable,
• Completed,
• O(n logn) time complexity,
• O ( n ) extra space for arrays,
• O ( logn ) extra space for linked lists,
• Does not require random access data,

How does it work?

In merge sort,

1. Firstly, unsorted array is divided into n sublist, until each sublist has only 1 element,
2. Then all elements are merged according to their value and new sorted arrays are created.

In the figure below, you can see animated merge sort example. Animated Merge Sort Example

Another example for merge sort is: Example For Merge Sort

Animation:

For better understanding, go to this animation page.

Pseudocode:

```# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
→ invariant: a[1..k] in final position
while i <= m,
a[k++] = b[i++]
→ invariant: a[1..k] in final position```

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/merge-sort

Figures from:  http://en.wikipedia.org

For more algorithms, go to Algorithms Section.

## Insertion Sort

Definition:

Insertion sort is a type of sort that simply sort an array.

It is less efficient than quick sort, merge sort.  However, it is simply implemented and it works for small data sets.

In worst and average case its time complexity is O(n^2) (square of n), in best case,  its time complexity is O(n).

• Stable,
• In-place : only needs O(1) additional memory,
• Online,
• Simple implementation,
• Efficient for small data sets.

How does it work?

Insertion sort iterates and growing a sorted list. In each iteration, it takes an element from list and finds the exact location of it in the list. After that it places in the correct place, iteration goes on until list is fully sorted.  In each  iteration, an element (x) places to the right place  and list becomes sorted like example below. becomes In  picture below, you can see the  insertion sort example. Insertion Sort Example

Animation:

For better understanding, go to this animation page.

Pseudocode:

```Insertion Sort ( X[ ] , n)
for j <- 2 to n
key <- X [ j ]
i <- j - 1
while i > 0 and X [ i ] > key
X [ i + 1 ] <- X [ i ]
i < - i -1
X [ i + 1 ] = key

```

References:

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), “2.1: Insertion sort”, Introduction to Algorithms (second ed.), MIT Press and McGraw-Hill, pp. 15–21.

Figures from:  http://en.wikipedia.org

For more algorithms, go to Algorithms Section.