정렬 알고리즘이란?

버블 정렬

  • 좌우에 있는 숫자를 비교해가며 정렬
  • 비교할 때마다 교체될 수 있으므로 O(n^2)이 된다.

선택 정렬

  • 수열을 선행탐색해서 최솟값을 찾아 왼쪽 끝과 교체한다.
  • 계속 끝까지 검색할 수 있으므로 O(n^2)

삽입 정렬

  • 맨 왼쪽 하나만 정렬이 끝났다고 생각하고 아직 작업하지 않은 나머지 영역의 맨 왼쪽의 값을 작업이 끝난 맨 오른쪽 숫자와 비교한다. 정렬된 영역에서 자기 자신보다 더 작은 게 나올 때까지 간다. 정렬된 크기를 늘려가는 방식. 정렬되지 않은 않은 가장 왼쪽부터 시작. 오른쪽으로 한 칸 가면서 정렬해나가는 방식.
  • 맨 끝까지 다 다르다면 선형시간으로 모두 다 비교해야되므로 시간복잡도는 O(n^2)이 된다

힙 정렬

  • 내림차순 힙으로 데이터를 꺼내고 역순으로 나열한다.
  • 한 번을 도는데 O(log n)이 걸리며 라운드 수가 n번이므로 O(n log n)이 된다.

병합 정렬

2분할, 2분할, 2분할… 가장 작은 하나씩 만들고 둘의 크기를 비교해서 정렬해서 합침. 합치면서 정렬. 그리고나서 처음 상태로 되돌아오면 됨.

  • n개의 숫자를 하나가 될 때까지 분할했을 때 층 수는 log n이 되고 n개 이므로 O(n log n)이 된다.

퀵 정렬

  • 기준이 되는 수(피봇)를 임의로 선택하고 피봇보다 작은 수들과 피봇 이상인 수들인 두 가지 그룹이로 나누어 배치한다. 재귀를 통해서 또 다시 피봇을 정하고 반복하면 된다.
  • 얘도 똑같이 반으로 나누므로 O(n log n)

위상 정렬

카운팅 정렬

● 횟수를 세서 정렬하는 방식. 가장 빠름. 쓸 수 있는 곳이 많진 않은듯?

● 인덱스대로 개수를 나누고 0개수부터 전에걸 더하는 방식. 전에것을 누적

● 이 항목이 마지막으로 올 수 있는 위치값

● 새로운 배열을 만들어서

● 자기 자리를 찾아서 넣어주고 하나씩 빼는 방식.

● 전체 n개 만큼 받은다음에 카운트를 셈.

● 카운트를 센 걸 가지고 입력의 max가 되면 거기까지만 . k까지. k번 횟수.

● 처음에 n, 마지막에 정렬해줄 때 n

● 정렬의 원소가 정수형으로 표현될 수 있는 얘일 때만 가능. 인덱스대로 쓰니까.