Sort Algorithm-정렬 알고리즘(2)

정렬 알고리즘

데이터 정렬이란 데이터를 일정한 순서로 배치하는 것을 말합니다. 정렬 알고리즘에는 다양한 방법이 있으며, 버블 정렬, 삽입 정렬, 병합 정렬 등이 있습니다. 

 

대표적인 정렬 알고리즘으로 세 가지 알고리즘이 있습니다.

• 버블 정렬
• 삽입 정렬
• 병합 정렬

삽입 정렬 

삽입 정렬은 카드 묶음을 정렬하는 것과 비슷한 알고리즘 입니다. 먼저 카드 묶음에는 정렬된 카드, 정렬되지 않은 카드들이 있습니다. 정렬되어 있지 않은 카드들의 묶음에서 카드를 하나씩 빼서 정렬된 카드 묶음에 올바른 위치에 넣는 알고리즘을 삽입 정렬이라고 합니다. 

 

삽입 정렬 코드를 보겠습니다. 

먼저 N과 n_list에 입력받을 리스트의 길이와 리스트의 요소들을 입력받습니다. insertion_sort라는 함수를 선언합니다. 먼저 1부터 a_list의 길이만큼 반복합니다. value 라는 값에 a_list[i]의 값을 담고 i가 0보다 크고(i가 0인 경우에는 a_list[i-1]이 존재하지 않기 때문)a_list[i-1]>value, 즉 value(a_list[i])값이 전의 요소값보다 작다면 a_list[i]의 위치에 더 큰 값을 두고 i를 1 감소시킵니다. 그리고 a_list[i]에 원래 value 값을 넣어서 두 개의 값이 바꿉니다. for문이 완료되면 a_list를 리턴합니다.

시간 복잡도

👉삽입 정렬의 시간 복잡도는 버블 정렬과 마찬가지로 0(n**2)입니다. 정렬되어 있거나 거의 정렬된 리스트에서 삽입 정렬의 시간 복잡도는 0(n)으로 매우 효율적이지만, 버블 정렬의 시간 복잡도는 항상 0(n**2)이므로 실무에서는 삽입 정렬은 사용해도 버블 정렬은 사용하지 않습니다.