나상민의 TIL

# 선택 정렬 (Selection Sort)

  1. 정의
  • 데이터 전체에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하는 방식으로 정렬을 하는 것
  1. 로직
    1. 주어진 리스트 중에 최소값을 찾는다.
    2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
    3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  2. 복잡도
    1. O(n^2)
  3. 예제

# 삽입 정렬 (Insertion Sort)

  1. 정의
  • 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식
  1. 로직
    1. 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
    2. n 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
    3. 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
  2. 복잡도
    1. O(n^2)
  3. 예제

# 버블 정렬 (Bubble Sort)

  1. 정의
  • 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식
  1. 로직
    1. 1번째와 2번째 원소를 비교하여 정렬한다.
    2. n-1번째와 n번째 원소를 비교하여 정렬한다.
    3. 정렬이 될때까지 반복한다.
  2. 복잡도
    1. O(n^2)
  3. 예제

# 합병 정렬 (Merge Sort)

  1. 정의
  • 하나의 리스트를 정렬하기 위해서 해당 리스트를 n개의 서브리스트로 분할하여 각각을 정렬한 수, 정렬된 n개의 서브리스트로 합병시켜서 정렬시키는 방법
  1. 로직
    1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
    2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
    5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.
  2. 복잡도
    1. O(nlogn)
  3. 예제

# 퀵 정렬 (Quick Sort)

  1. 정의
  • 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법
  1. 로직
    1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
    2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
    3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다
  2. 복잡도
    1. O(nlogn)
  3. 예제

# 힙 정렬 (Heap Sort)

  1. 정의
  • 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
  1. 로직
    1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
    2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
    3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
    4. 2와 3을 반복한다
  2. 복잡도
    1. O(nlogn)
  3. 예제

←