[알고리즘] 정렬 ( 버블정렬, 선택정렬, 삽입정렬, 병합정렬)

정렬

버블정렬

요소들이 마치 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고하여 버블정렬이라고 부른다.

배열첫인덱스부터 끝인덱스까지 순차적으로 비교해가면서 순회하는 반복문을 사용

끝인덱스에 가장 큰수를 넣었다면 다시 처음부터 끝에 넣은 큰수 인덱스제외 비교해가며 순회한다.

시간복잡도는 O(N^2)

 

선택정렬(Selection Sort)

인덱스 0부터 배열의 길이만큼의 값을 비교하여 전체중 최소값의 인덱스를 기억하고 그것을 순차적으로 왼쪽부터 정렬하는것

시간복잡도는 O(N^2)

삽입정렬(Insertion Sort)

전체에서 필요할때만 하나씩 올바른 위치에 “삽입"하는 방식

인덱스0 부터 차례로 정렬을 하기때문에 만약 그다음 for문에 해당하는 인덱스값이 그 앞 인덱스에 해당하는 값과 비교하여 더 크다면 그 앞에있는 인덱스해당하는 값들을 비교할필요없기때문에 break 문을 건다. 따라서 시간복잡도는 O(N^2)이거나 만약 정렬이 되어있다면 O(N) 이 될수있다.

병합정렬(Merge sort)

면접에서 직접 구현해보라는 방법중하나.

병합정렬은 배열의 앞부분고 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

예를들어 A 라고 하는 배열이 [1,2,3,5] 로 정렬 되어있고 B 라는 배열이 [4,6,7,8] 이 있다면 이 두집합을 합쳐가면서 정렬하는 방법이다.

분할정복(divide and conquer)