240412-TIL

4월 12일

 

오늘도 단골 기술 면접 질문에 대해 정리해봐야겠다

 

정렬 알고리즘이란?

질문 : 정렬 알고리즘이란 무엇이며, 사용 이유에 대해 설명해주세요. 

 

 

일단 정렬 알고리즘이 어떤게 있는지부터 알아봐야한다. 

 

위 그림은 정렬알고리즘이라고 검색하면 킹무위키에서 보여주는 세상 모든 정렬 알고리즘이다

 

너무많기 때문에 자주 사용하고 자주 들어본것들만 추려보자

 

1. 버블 정렬

 

버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬이라고 한다.

 

시간 복잡도는 O(N2) 이지만 연산 수가 많아 정렬 알고리즘에서는 가장 느리다고 한다.

 

2. 선택 정렬

 

선택 정렬은 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 정렬이다.

 

 

선택 정렬의 시간 복잡도는 O(N2) 이다 시간복잡도로 보면 선택 정렬도 좋은 알고리즘은 아니다.

 

3. 삽입 정렬

 

삽입 정렬은 데이터를 순서대로 뽑아서 위치를 뽑아 삽입하는 정렬이다.

 

 

삽입 정렬도 마찬가지 O(N2)로 좋은 알고리즘은 아니다.

 

4. 합병 정렬

 

합병 정렬은 선택,삽입,버블 정렬과 다르게 순서가 있다.

 

분할,정렬,결합순으로 진행되고 데이터 배열을 2개 이상의 부분 배열로 분할 -> 부분 배열에서 정렬 -> 재결합 -> 다시 정렬 순으로 이루어진다

 

 

합병 정렬의 시간 복잡도는 O(nlogn) 데이터를 정확히 반으로 나누고 정렬하기 때문에 일정한 시간 복잡도를 유지하는 장점이 있지만 다른 알고리즘과 비교했을때 O(n)의 메모리가 추가로 필요하다고 한다.

 

5. 힙 정렬

 

힙 정렬은 이진트리 기반의 트리형 자료구조이다 내림차순 정렬은 최대 힙 오름차순 정렬은 최소힙을 구성하면 된다.

 

 

힙 정렬도 시간복잡도는 합병 정렬과 같은 O(nlogn)이다 특징은 완전 이진트리를 사용한다고 한다.

 

6. 퀵 정렬

 

퀵 정렬은 데이터 중 임의의 기준값을 정해서 두 분류로 나눈다 기준값을 피벗으로 두고 왼쪽은 피벗보다 작은 값

 

오른쪽은 피벗보다 큰 갑슬 배치하고 더 이상 집합을 나눌수 없을때 재귀적으로 실행된다고 한다.

 

 

퀵 정렬의 시간복잡도는 O(nlogn) Average,Best는 동일하지만 Worst의 경우 O(n2)이고 이미 정렬된 데이터라면 매우 비효율적으로 작용한다.

 

정렬 알고리즘을 이렇게 알아보았는데

 

그렇다면 이런 정렬 알고리즘을 왜 사용할까?

 

바로 이진 탐색 알고리즘을 사용하기 위해서라고 한다.

 

정렬 알고리즘으로 일단 한번 데이터를 정렬해 놓은다면 이진 탐색이라는 강력한 알고리즘을 사용하여 데이터를 탐색 할 수 있다.

 

이진 탐색은 최악의 경우라도 O(log n)의 성능을 보인다.

오늘은 탐색 알고리즘이 어떤게 있는지

 

왜 사용하는지에 대해서 알아보았다.

 

잘 기억해두자

 

4월 12일 TIL은 여기서 마치도록 하자