[개념정리] 정렬 _1(버블 정렬, 단순 선택 정렬, 단순 삽입 정렬)

정렬이란?

Key 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업.

 

- 오름차순정렬 : 키 값이 작은 데이터를 앞쪽에 놓은 경우

- 내림차순정렬 : 키 값이 큰 데이터를 앞쪽에 놓은 경우

 

안정된 정렬 : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것.

아래의 예시로 설명하자면 키란 5를 의미하고 요소는 하트와 스페이드를 의미한다. 오름차순으로 정렬하였음에도 (5,하트) 는 여전히 (5, 스페이드) 앞에 위치해있다.

출처 : https://en.wikipedia.org/wiki/Sorting_algorithm#/media/File:Sorting_stability_playing_cards.svg

내부 정렬 : 하나의 배열에서 작업할 수 있는 경우 사용하는 알고리즘 (버블, 선택, 삽입, 셸, 퀵, 병합, 힙, 도수 정렬 등등은 모두 내부정렬이다.)

외부 정렬 : 하나의 배열에서 작업할 수 없는 경우 사용하는 알고리즘 (외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 작업을 위한 파일 등이 필요하고 복잡하다.)

 

버블정렬이란?