정렬 알고리즘(버블, 선택, 삽입)

정렬 알고리즘

특정 값을 기준으로 데이터를 순서대로 배치하는 알고리즘

 

1. 구현 난이도는 쉽지만, 속도는 느린 알고리즘

 - 버블정렬, 삽입정렬, 선택 정렬

 

 1.1 버블 정렬

  인접한 데이터를 비교하며 자리를 바꾸는 방식

  시간복잡도 : O(N^2)

 

앞에 두수를 비교해서 자리를 교체 마지막 자리는 가장 큰 수가 됨으로 한번 돌때마다 -1번씩 횟수가 줄어듬

  1.2 삽입 정렬

   앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식

   시간복잡도 : O(N^2)

   

arr[1]번을 기준으로 앞과 비교하면서 작으면 교체

  1.3 선택 정렬

   최소 또는 최대값을 찾아서 정렬하는 방식

   시간복잡도 : O(N^2)

 

2. 구현 난이도는 조급 어렵지만, 일반적으로 속도는 빠른 알고리즘

 - 합병정렬, 퀵정렬, 트리정렬

 

  2.1 합병 정렬

   배열을 계속 분할해서 길이가 1 이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식

   시간복잡도 : O(nlogn)

  2.2 힙 정렬

   기존 배열을 최대 힙으로 구조 변경 후 정렬 진행

   시간복잡도 : O(nlogn)

 

  2.2 퀵 정렬

   임의의 기준 값(pivot)을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식

   시간복잡도 : O(n^2) -> 기존값이 최소값 또는 최대값으로 지정하는 경우 (최악의 경우)

 

 

 

3. 하이브리드 정렬

 - 팀정렬, 블록 병합 정렬, 인트로 정렬

 

4. 기타 정렬 알고리즘

- 기수정렬, 카운팅 정렬, 셀 정렬, 보고 정렬

 4.1 기수정렬

  낮은 자리 수부터 정렬하는 방식

  각 원소 간의 비교 연산을 하지 않아 빠른 대신 , 기수 테이블을 위한 메모리가 필여

  알고리즘 복잡도 : O(dn) d : 최대 자릿수 

 

 

 4.2 계수 정렬

  숫자 끼리 비교하지 않고 카운트를 세서 정렬하는 방식

  카운팅을 위한 메모리 필요

  알고리즘 복잡도 : O(K + n) K : 최대 자릿수 

 

 4.2 셸 정렬

  삽입 정렬의 약점을 보완한 정렬

  오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비교하며 모두 교환

  이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교

  알고리즘 복잡도 : O(n^2) 최악의 경우 

  알고리즘 복잡도 : O(K + n) K : 최대 자릿수 

 

최악 , 최적 경우에 따른 시기ㅏㄴ 복잡도