자료구조 22강 - 정렬(Sorting)

리스트 연산

 

- 리스트에 원소를 추가 또는 제거하고 원하는 원소를 검색

- 제약점 : 정렬된 리스트만을 요구

ex1. 8 19 23 34 64 - O

ex2. 34 64 19 8 23 - X

→ 정렬되지 않은 리스트는 정렬해야한다

 

 

정렬(Sorting)

 

- 데이터를 정해진 키에 따라서 크기 순으로 배열하는 것

→ 오름차순 (ascending order) / 내림차순 (descending order)

 

 

정렬 알고리즘의 성능

 

- 정렬할 데이터 개수가 n개일 때 O(f(n))으로 표시

- O(n²) 정렬 알고리즘 : 버블정렬, 삽입정렬, 선택정렬 등

- O(n log n) 정렬 알고리즘 : 합병 정렬, 쾌속 정렬