(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘

https://youtu.be/KGyK-pNvWos?feature=shared

 

 

• 선택 정렬

- 현재 상태에 가장 작은 원소를 앞쪽으로 보냄 

- N번만큼 가장 작은 수를 찾아서 맨 앞으로 보냄

- O(N^2) 

 

array[i], array[j] = array[j], array[i] # swap 

 

 

• 삽입 정렬

- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

- 앞쪽에 있는 원소들이 정렬되어 있다고 판단하고 현재 데이터의 위치를 판단 0

- 선택 정렬에 비해 구현 난이도는 높지만, 일반적으로 더 효율적

- O(N^2), 최선의 경우 O(N)

 

 

• 퀵 정렬

- 피벗 설정 후 , 왼쪽에서 부터 피벗보다 큰 값 <-> 오른쪽에서부터 피벗보다 작은 값 (위치 서로 변경)

- 위치가 엇갈리는 경우 : 피벗 <-> 작은 데이터 (위치 서로 변경)

- 피벗에 기준으로 : 왼쪽과 오른쪽으로 나눠서 재귀적으로 정렬 수행 

 

- 평균 : O(NlogN), 최악의 경우 : O(N^2)

 

 

• 계수정렬

- 가장 작은 데이터부터 가장 큰 데이터의 범위가 모두 담길 리스트 생성 (인덱스사용) 초기화:0

- 데이터의 값을 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 시킴 

- 결과 확인시 리스트의 첫 번째 데이터 부터 하나씩 그 값만큼 반복하여 인덱스를 출력 

 

- 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적 (성적) 

 

 

 

표준정렬 라이브러리 :

array.sort() 

array.sort(reverse=True)

result = sorted(array, key=lamda x: x[1], reverse=True)