[백엔드] 기술 면접 Top30 - #30 정렬 알고리즘에 대해서

정렬 알고리즘

 

 

버블 정렬 (Bubble Sort)

• 버블 정렬은 간단한 정렬 알고리즘 중 하나로,
  인접한 두 요소를 비교하고 필요한 경우 위치를 교환하는 방식으로 동작한다.
• 반복문을 사용하여 모든 요소를 순회하며 가장 큰(또는 작은) 요소가 배열의 끝으로 이동한다.
• 이러한 반복을 통해 정렬이 이루어진다.
  
  

삽입 정렬 (Insertion Sort)

• 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누며,
  정렬되지 않은 부분의 요소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작한다.
• 배열을 순회하면서 현재 요소를 정렬된 부분에 삽입할 위치를 찾고, 요소를 삽입한다.
• 이 과정을 반복하여 전체 배열이 정렬된다.
  
  

힙 정렬 (Heap Sort)

• 힙 정렬은 주어진 배열을 힙으로 변환한 다음,
  힙에서 최댓값(또는 최솟값)을 추출하여 배열의 뒤에서부터 저장하는 방식으로 정렬한다.
• 기본적인 아이디어는 배열을 최대 힙으로 만들고, 루트 노드(최댓값)를 배열의 뒷부분에 저장한 다음,
  힙 크기를 하나 줄이고 다시 최대 힙 속성을 유지하면서 루트 노드를 빼내어 배열의 앞부분에 저장한다.
• 이 과정을 반복하여 전체 배열이 정렬된다.
  
  

병합 정렬 (Merge Sort)

• 병합 정렬은 분할 정복(divide and conquer) 알고리즘의 예로, 배열을 반으로 나눈 뒤 각 부분을 재귀적으로 정렬하고,
  정렬된 부분을 병합하여 전체 배열을 정렬한다.
• 이 알고리즘은 안정적이며, 대규모 데이터 집합에도 효과적으로 동작한다.
  
  

퀵 정렬 (Quick Sort)

• 퀵 정렬은 빠른 정렬 알고리즘 중 하나로,
  피벗(pivot) 요소를 선택하고 피벗을 기준으로 작은 요소와 큰 요소를 분할하여 정렬한다.
• 피벗의 선택과 분할 과정을 반복하여 전체 배열을 정렬한다.
• 이 알고리즘은 평균적으로 매우 빠르게 동작하며, 효율적이다.
  
  

선택 정렬 (Selection Sort)

• 선택 정렬은 배열을 두 부분으로 나누는 방식으로 동작한다.
• 하나는 정렬된 부분, 다른 하나는 정렬되지 않은 부분이다.
• 정렬되지 않은 부분에서 가장 작은 요소를 선택하여 정렬된 부분의 끝으로 이동시킨다.
• 이 과정을 반복하여 전체 배열이 정렬된다.
  
  

요약

버블 정렬은 인접한 요소를 비교하며 정렬하는 간단한 알고리즘.
선택 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 작은 요소를 선택해 정렬한다.
삽입 정렬은 요소를 정렬된 부분에 삽입하는 방식으로 동작한다.
병합 정렬은 배열을 분할하고 재귀적으로 정렬한 후 병합하여 정렬한다.
힙 정렬은 힙 자료구조를 활용하여 최대값을 추출하며 정렬하며, 효율적이고 인-플레이스 정렬이다.