[코드잇 알고리즘] 정렬 알고리즘 & 좋은 알고리즘 평가방법

정렬 알고리즘이란?

가장 기초가 되는 알고리즘의 종류로써 파이썬에서는 이미 sorted or .sort() 함수가 내장되어 있습니다.

 

1. 선택정렬 (Selection sort)

    각 위치에 어떤 값이 들어갈지 찾습니다. 가장 작은 최소 값인지를 판단해서 index를 하나씩 채워나가는 방식입니다.

    [1. 5. 3 .0 ] 리스트에서 가장 최소 값은 0 이기 때문에 0을 index [0]에 위치 시킵니다. --> [0, 1, 5, 3]

    0 다음으로 '1'이 가장 최소 값이므로 그대로 index[1]에 위치됩니다.

    다음으로 [0, 1, 5, 3 ] 리스트에서 3이 가장 최소값이기 때문에 [0, 1, 3, 5]로 '3'을 index[2]에 위치 시킵니다.

 

2. 삽입정렬 (Insertion Sort)

    각 값이 어떤 위치에 들어갈지 찾습니다.

    [4, 2, 7, 1, 9, 3]에서 '4' 값이 바로 옆에 위치한 '2'보다 크므로 자리를 바꿉니다. --> [2,4,7,1,9,3]

    '1' 값은 7보다 작으므로 좌측으로 이동하며, '4'보다 작고, '2'보다 작기 때문에 제일 좌측으로 이동합니다. --> [1,2,4,7,9,3]

 

이외에도 'Bubble sort', 'Shell sort', 'Merge sort', 'Heap sort', 'Quick sort' 등이 정렬 알고리즘으로 있습니다.

 

 

좋은 알고리즘이란?

시간 복잡도가 낮은 알고리즘일수록 효율적입니다.

시간 복잡도를 평가하기 위해서는 '거듭제곱'과 '로그' 개념을 적용해야합니다.

 

Logab => b를 a로 몇번 나누어야 1이 될까? 라는 해석으로 볼 수 있습니다.

Ex) Log24 = 2 에서 4를 2로 두 번 나누면 1이 된다고 해석할 수 있습니다.

 

알고리즘에 대한 소요시간을 input의 크기(리스트 길이)로 환산해서 나타낼 수 있습니다.

 

표준방식인 점근표기법을 활용해서 시간 복잡도를 계산합니다.