[동빈나 - 이것이 코딩테스트다] 정렬

array = [7, 1, 5, 9, 0, 3, 6, 2, 4, 8]

for i in range(len(array)):
  min_index = i
  for j in range(i+1, len(array)):
    if array[min_index] > array[j]:
      min_index = j
  array[i], array[min_index] = array[min_index], array[i]

print(array)

Output = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
  for j in range(i, 0, -1):
    if array[j-1] > array[j]:
      array[j-1], array[j] = array[j], array[j-1]
    else:
      break

array

Output = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
  if len(array) <= 1:
    return array

  pivot = array[0]
  tail = array[1:]

  left_side = [x for x in tail if x <= pivot]
  right_side = [x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))
# 분할 방식이 좀 달라 비교 연산횟수가 많아지므로 비효율적이지만 파이썬스럽고 직관적인 코드

Output = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0]*(max(array)+1)

for i in range(len(array)):
  count[array[i]] += 1

for i in range(len(count)):
  for j in range(count[i]):
    print(i, end=' ')

Output = 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9