Sorting Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is insertion sort?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Pros of insertion sort?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Cons of insertion sort?

A
  • inefficient on large data set or if the data set is reverse order
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is selection sort?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Pros of selection sort?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Cons of selection sort?

A
  • inefficient on large data set
  • not adaptive
  • not stable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Code for selection sort

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

for (i = 0; i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Code for insertion sort

A
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;
  }
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is merge sort?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Pros of merge sort?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Cons of merge sort?

A
  • not as fast as quick sort (on average)

- requires as much memory as the original array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Code for merge sort

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is quick sort?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Pros of quick sort?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Cons of quick sort?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Code for quick sort.

A
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
17
Q

What is heap sort?

A

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(n
log n)

18
Q

What is the heap property?

A

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.

19
Q

Pros of heap sort?

A
  • 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
20
Q

Cons of heap sort?

A
  • Not as fast on average as Quick sort

- Quite a lot of code to implement the heap operations

21
Q

Code for heap sort.

A
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]
22
Q

What is bubble sort?

A

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)

23
Q

Pros of bubble sort?

A
  • 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
24
Q

Cons of bubble sort?

A
  • probably the slowest sort ever invented
25
Q

Code for bubble sort

A
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;
                  }
            }                
      }
}
26
Q

What is shell sort?

A

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)

27
Q

Pros of shell sort?

A
  • 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
28
Q

Cons of shell sort?

A
  • 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.
29
Q

Code for shell sort

A
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;
  }
}