【컴퓨터과학개론】정렬 알고리즘

안녕하세요 【키보드 워리어】

 

⌨🗡🧑

블로그 방문자 여러분, 안경닦이입니다.

 

---

 

 

정렬 알고리즘

 

알고리즘은 주어진 문제에 대한 하나 이상의 출력 결과를 생성하기 위해

모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것입니다

 

 

그중에서 정렬(sort)이란 컴퓨터 과학에서 가장 많이 사용되는 응용 중의 하나로서, 주어진 데이터를 일정한 기준에 따라 순서 있게 재배열하는 연산입니다

 

 

정렬 방법은 정렬이 수행될 당시 데이터가 어디에 저장되어 있느냐에 따라 크게 두 가지 방법,

즉 내부 정렬(internal sort)과 외부 정렬(external sort)로 나눌 수 있는데요

 

 

내부정렬은 정렬할 데이터의 양이 충분히 크지 않기 때문에 모든 데이터를 주기억장치에 적재해서 정렬하는 방법으로

선택 정렬,퀵 정렬, 합병정렬합병 정렬, 히프정렬히프 정렬, 계수정렬계수 정렬, 기수정렬 등이 있고요

 

 

외부 정렬은 데이터가 많아 전체 데이터를 보조기억장치에 저장하고

 

 

그중의 일부 데이터를 번갈아 가면서 주기억장치에 적재해 정렬을 수행하는 방식으로

 

 

대치 선택 방법, 다단계 합병 정렬 등이 있습니다

 

 

내부 정렬 중에서 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 히프 정렬 알고리즘은

데이터의 키 값(key)을 직접적으로 비교하며 정렬하고

 

계수 정렬, 기수 정렬 등은 키들의 비교가 아닌 값의 분포를 이용하여 정렬을 수행합니다

 

키값이 뭘까?

2022.08.25 - [개발 관련 공부/SQLite] - 【SQLite】left, inner문으로 테이블 합쳐보자

 

 

먼저 선택 정렬은 주어진 원소 중에서 가장 작은 키 값을 갖는 원소를 선택하여 차례대로 나열하는 정렬 방식입니다

최악/최선/평균 수행 시간은 모두 언제나 동일한 O(N2승)을 가지는데 간단하고 데이터 수가 적은 경우에 효율적입니다

 

최악/최선 알고리즘

2022.08.05 - [개발 관련 공부/알고리즘] - 【알고리즘】시간복잡도와 공간복잡도, 표기법

 

 

버블 정렬은 주어진 리스트의 왼쪽에서부터 모든 인접한 두 원소를 차례대로 비교하면서

왼쪽의 값이 더 큰 경우에는 오른쪽의 값과의 자리바꿈을 통해 정렬해 나가는 방법을 일컫습니다

 

 

리스트에서 가장 큰 값은 비교 과정에서 항상 자리바꿈이 일어나기 때문에

첫 번째 단계를 마치면 리스트의 맨 오른쪽에 위치하고

두 번째 단계에서는 두 번째로 큰 값이 리스트 오른쪽에서 두 번째 자리에 위치합니다.

 

 

최악의 경우 이러한 단계를 N-1회 거쳐서 주어진 리스트가 오름차순으로 정렬됩니다

그래서 데이터의 입력 순서에 민감하여 최선의 수행 시간은최악의 경우로서 O(n2승)을 갖습니다

 

 

삽입 정렬은 아주 간단한 정렬 방법으로 주어진 원소들을 하나씩 뽑은 후,

나열된 원소들이 항상 정렬된 형태를 가지도록 뽑은 원소를 바른 위치에 삽입하여 나열하는 방식입니다

 

 

버블 정렬과 마찬가지로 데이터의 입력 순서에 민감하여 최선의 수행 시간은최악의 경우로서 O(n2승)을 갖는다.

 

 

퀵 정렬은 피벗이라고 불리는 특정한 키 값을 기준으로

주어진 입력 리스트를 두 개의 서브 리스트로 분할한 후,

각 서브 리스트에 대해 독립적으로 퀵 정렬을 순환적으로 적용시켜 정렬하는 방식입니다.

 

 

합병 정렬은 피벗을 기준으로 동일한 크기의 두 서브 리스트로 분할하기 때문에 두 서브 리스트의 크기가 다를 수 있고,

이것 때문에 최악의 시간 복잡도 O(n2승)을 갖습니다.

 

 

분할 정복 방법이 적용된 알고리즘이며 분할 한 서브 리스트를 순환적으로 정렬하고 난 후

부분 배열을 합병하여 하나로 나열하는 방식입니다 (분할>정복>결합)