오래전에 정처기 공부할때 정리했던것이다.
Sort 알고리즘
1. 삽입 정렬
5 2 4 1 7
현재 인덱스보다 앞에 있는 숫자와 비교를 통해 자신이 들어갈 자리를 찾는다.
진행 1 결과 25417 (52417에서 2를 기준으로 5와 자리 바꿈, 앞에 있는 숫자와 비교)
진행 2 결과 24517 (25417에서 4를 기준으로 5번과 자리 바꿈)
진행 3 결과 12457 (24517에서 1를 기준으로 245 모두 우측으로 넣는다.)
...
최상의 경우 0(N) 평균적으로 0(N^2)
2. 선택 정렬
5 2 4 1 7
비교를 통해 비교 데이터들 중 가장 작은 값을 뽑아나감으로 정렬
여기서 헷갈릴만한건..작은값을 앞으로 밀어 넣는것이 아닌 자리 교체를 한다는 것이다
진행 1 결과 15247 (52417에서 가장 작은 수인 1를 선택해서 가장 왼쪽에 넣음)
진행 2 결과 12547(15247에서 가장 작은 수인 2를 선택해서 0번째 제외해서 가장 왼쪽에 넣음)
진행 3 결과 12457 (12547에서 가장 작은 수인 4를 선택해서 1번째 제외해서 가장 왼쪽에)
진행 4 결과 12....
0(N^2)의 성능
3. 버블 정렬
52417
N개의 데이터가 있을때 n-1번의 비교를 통해 진행함
진행 1 결과 24157 (52417에서 옆에 있는 애들끼리 비교해서 바꿔줌)
진행 2 결과 21457(옆에 있는 애들끼리 비교해서 바꿔줌)
진행 3 결과 12457
진행 4 결과 12457
0(N^2)의 성능
4. 병합 정렬
n개의 데이터를 이분법을 통해 n/2개로 쪼개고 그 n/2개를 또 n/4의 4개로 쪼갠다.
합칠때 데이터의 크기를 비교하여 합치는 과정으로 정렬함
O(Nlog^2N)을 가지는 특징이 있음
단순(구현 간단)하지만 비효율적인 방법
삽입 정렬, 선택 정렬, 버블 정렬
복잡하지만 효율적인 방법
퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
'STUDY > Algorithm' 카테고리의 다른 글
| Algorithm - 에라토스테네스의 체 (효율성 좋게 소수 찾기) (0) | 2022.05.12 |
|---|
