Sorting Algorithms

Question 1

What is insertion sort?

Answer 1

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. Array is imaginary divided into two parts - sorted one and unsorted one. At the beginning, sorted part contains first element of the array and unsorted one contains the rest. At every step, algorithm takes first element in the unsorted part and inserts it to the right place of the sorted one. When unsorted part becomes empty, algorithm stops.

Best case: O(n) (list is already sorted)
Worst case: O(n^2)

Question 2

Pros of insertion sort?

Answer 2

• simple implementation
• efficient for small data sets
• more efficient than bubble sort or selection sort
• adaptive (i.e. effective for sets that are already substantially sorted.)
• stable (i.e. doesn’t change the relative order of elements with equal keys)
• does sort in place
• very low overhead

Question 3

Cons of insertion sort?

Answer 3

• inefficient on large data set or if the data set is reverse order

Question 4

What is selection sort?

Answer 4

Selection sort is a sorting algorithm, specifically an in-place comparison sort. The idea of selection sort is rather simple: repeatedly find the next largest (or smallest) element in the array and move it to its final position in the sorted array.

Assume that the array should be sorted in increasing order, i.e. the smallest element at the beginning of the array and the largest element at the end. Begin by selecting the largest element and moving it to the highest index position. Do this by swapping the element at the highest index and the largest element. Then reduce the effective size of the array by one element and repeat the process on the smaller (sub)array. The process stops when the effective size of the array becomes 1 (an array of 1 element is already sorted).

Best case: O(n^2)
Worst case: O(n^2)

Question 5

Pros of selection sort?

Answer 5

• has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

Question 6

Cons of selection sort?

Answer 6

• inefficient on large data set
• not adaptive
• not stable

Question 7

Code for selection sort

Answer 7

void selectionSort(int numbers[], int array_size)
{
  int i, j;
  int min, temp;

for (i = 0; i

Question 8

Code for insertion sort

Answer 8

void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i = 1; i  0) && (numbers[j − 1] > index))
          {
                   numbers[j] = numbers[j − 1];
                   j = j − 1;
          }
          numbers[j] = index;
  }
}

Question 9

What is merge sort?

Answer 9

Merge sort (also commonly spelled merge sort) is an O(n log n) comparison-based sorting algorithm. Steps for the merge sort algorithm are:

1. Divide Step: If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
2. Conquer Step: Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
3. Combine Step: Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

Best case: O(n * log n)
Worst case: O(n*log n)

Question 10

Pros of merge sort?

Answer 10

• very predictable
• stable
• it can be applied to files of any size.
• reading of the input during the run-creation step is sequential ==> Not much seeking.
• reading through each run during merging and writing the sorted record is also sequential. The only seeking necessary is as we switch from run to run.
• if heapsort is used for the in-memory part of the merge, its operation can be overlapped with I/O
• Since I/O is largely sequential, tapes can be used.

Question 11

Cons of merge sort?

Answer 11

• not as fast as quick sort (on average)

- requires as much memory as the original array

Question 12

Code for merge sort

Answer 12

void m_sort(int numbers[], int temp[], int left, int right) {
int mid;
if (right > left) {
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}

void merge(int numbers[], int temp[], int left, int mid, int right) {

  int i, left_end, num_elements, tmp_pos;
  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

   while ((left

Question 13

What is quick sort?

Answer 13

Quick sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Quick sort is a divide and conquer algorithm. Quick sort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quick sort can then recursively sort the sub-arrays.

The steps are:

1. Pick an element, called a pivot, from the array.
2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Best case: O(n*log n)
Worst case: O(n^2)

Question 14

Pros of quick sort?

Answer 14

• It is in-place since it uses only a small auxiliary stack.
• It requires only n log(n) time to sort n items.
• It has an extremely short inner loop
• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Question 15

Cons of quick sort?

Answer 15

• It is recursive. Especially if recursion is not available, the implementation is extremely complicated.
• It requires quadratic (i.e., n^2) time in the worst-case.
• It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.

Question 16

Code for quick sort.

Answer 16

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

  while (i  pivot)
              j--;
        if (i

Question 17

What is heap sort?

Answer 17

Heap sort is a comparison-based sorting algorithm. Heap sort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Best case: Ω(n), O(nlog n)
Worst case: O(nlog n)

Question 18

What is the heap property?

Answer 18

In a heap, for every node i other than the root, the value of a node is greater than or equal (at most) to the value of its parent.
A[PARENT (i)] ≥ A[i]
Thus, the largest element in a heap is stored at the root.

Question 19

Pros of heap sort?

Answer 19

• Guaranteed to be O(n.log n)
• One of the few non-recursive O(n.log n) sorts
• Fairly easy to debug, because it is non-recursive and because it consists of two smaller and unrelated parts

Question 20

Cons of heap sort?

Answer 20

• Not as fast on average as Quick sort

- Quite a lot of code to implement the heap operations

Question 21

Code for heap sort.

Answer 21

void heapSort(int numbers[], int array_size)
{
  int i, temp;

//heapify
for (i = (array_size / 2)-1; i >= 0; i–)
siftDown(numbers, i, array_size);

  //sortdown
  for (i = array_size-1; i >= 1; i--)
  {
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}

//sink
void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2  numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

if (numbers[root]

Question 22

What is bubble sort?

Answer 22

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Best case: O(n)
Worst case: O(n^2)

Question 23

Pros of bubble sort?

Answer 23

• simple to implement and understand, but not much more so than several more efficient sorts
• will be very quick on an already sorted list
• stable
• adaptive

Question 24

Cons of bubble sort?

Answer 24

• probably the slowest sort ever invented

Question 25

Code for bubble sort

Answer 25

``` public void bubbleSort(int[] arr) { boolean swapped = true; int j = 0; int tmp; while (swapped) { swapped = false; j++; for (int i = 0; i arr[i + 1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; swapped = true; } } } } ```

Question 26

What is shell sort?

Answer 26

Shell sort is a simple extension of Insertion sort. Its speed comes from the fact that it exchanges elements that are far apart (the insertion sort exchanges only adjacent elements). Best case: O(n*log^2 n) Worst case: O(n^2)

Question 27

Pros of shell sort?

Answer 27

- Usually much faster than regular insertion sort for very little extra work - The fastest of the non-recursive sorts shown here - Easy to get working

Question 28

Cons of shell sort?

Answer 28

- Running time is slightly sensitive to the data (but far less so than binary tree sort or Quick sort) - Not quite as fast as ultra-fast sorts like Quick sort - If you mess up the sequence, you get a sort that will still work but is slow.

Question 29

Code for shell sort

Answer 29

``` void shellSort(int numbers[], int array_size) { int i, j, increment, temp; ``` ``` increment = 3; while (increment > 0) { for (i=0; i = increment) && (numbers[j-increment] > temp)) { numbers[j] = numbers[j - increment]; j = j - increment; } numbers[j] = temp; } if (increment/2 != 0) increment = increment/2; else if (increment == 1) increment = 0; else increment = 1; } } ```