Vincec's Dimension

# Sort Review

Word count: 733 / Reading time: 5 min
2019/06/12 Share

Basic for search, with for loops

## Bubble Sort

(exchange) rearrange pairs of elements which are out of order, until no such pairs remain.

• two for search(pos from end to 0, one from 0 to pos)
• compare value with next, if smaller, swap value
• first need sort
• binary Search

## Selection Sort

extract the largest element from the list, exchange with the last element in the current list, and repeat.

• look for the smallest from pos(init to 1) to end
• swap smallest with (pos-1)
• make pos move to next

## Insertion Sort

putting an element in the appropriate place in a sorted list yields a larger sorted list.

• start from second and always keep sorted
• if next value is smaller than keep the value, and move all the sorted value to right one by one and then insert to right posiiton

## Quick Sort

divide-and-conquer algorithm. Its average running time is O(N log N).

Figure Courtesy of Weiss Data Structures Book

## Bucket Sort

separate into piles based on the first letter, then sort each pile.
place items into various buckets based on a key or partial information about a key.

radix sort can be applied to data that can be compared partially like integers of characters.
Radix sort cannot be applied to data that needs to be compared as a whole

The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

## Merging Sort

Two sorted lists can be easily combined to form a sorted list.

# Reference

Author: VINCEC

Copyright license: The article usingCC licensing 4.0