Sorting

20 Aug 2022 in Notes / Codingtest / Algorithms Last modified at: 2022-09-02

A page showing how regular markdown content is styled in Hydejack.

• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort

Bubble Sort

.

VisuAlgo - Bubble Sort

• compares two at a time, several rounds
• guarantees largest data at the end every round (in yellow)
  • sorted from tail
• IF NO SWAPS occurred during the whole round, break to end faster

def bubblesort(data):
  for i in range(len(data)-1):
    no_swap = 1 # to break if no swaps 
    for j in range(len(data)-i-1): # no need to compare after the 'yellow' part (already sorted)
      if data[j+1] < data[j]:
        data[j+1], data[j] = data[j], data[j+1]
        no_swap = 0
    if no_swap:
      break
  return data

Time Complexity
Worst Case	\(O (n^2)\)
Best Case	\(O(n)\) - already sorted (no_swap = 1)

Selection Sort

.

VisuAlgo - Selection Sort

• select the minimum and bring it to the front
  • sorted from the front

def selectionsort(data):
  for i in range(len(data)-1):
    index_of_min = i
    for j in range(i+1, len(data)): 
      if data[j] < data[index_of_min]:
        index_of_min = j
    data[i], data[index_of_min] = data[index_of_min], data[i]
  return data

Time Complexity
Worst = Best Case	\(O (n^2)\)

Insertion Sort

.

VisuAlgo - Insertion Sort

• choose and swap with the prior data if it is not in order (until it finds place)
  • sorted from the front

def insertionsort(data):
    for i in range(len(data)):
        for j in range(i, 0, -1):
            if data[j] < data[j-1]:
                data[j], data[j-1] = data[j-1], data[j]
            else:
                break        
    return data

Time Complexity
Worst Case	\(O (n^2)\)
Best Case	\(O(n)\) - already sorted (no_swap = 1)

• bubble sort와 동일

Quick Sort

정렬 알고리즘의 꽃

.

VisuAlgo - Quick Sort

• 하 개귀찮아…

Merge Sort

.

VisuAlgo - Merge Sort