j-engine 님의 블로그

버블 정렬은 시간 복잡도가 O(n^2)인 상당히 느린 알고리듬이지만 코드가 매우 단순합니다. 기본적으로 배열의 두 수(a, b)를 선택한 뒤, 이 두 수가 정렬되어 있다면 넘어가고 아니라면 두 수를 바꾸는 방식(Swap)으로 진행됩니다.이 비교를 배열의 처음부터 끝까지 반복하면 오름차순으로 정렬할 때 가장 큰 값이 배열의 맨 마지막이 됩니다.다시 한번 비교를 진행하면 2번째로 큰 값이 가장 큰 값의 앞으로 오게됩니다.배열에 아무 변화가 없을 때까지 반복하거나 더는 비교할 수 없을 때까지 진행이 되었다면 정렬이 끝이 납니다. void BubbleSort(vector& nums) { int n = nums.size(); for (int i = n - 1; i > 0; i--) { bool swappe..

선택 정렬은 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2)만큼의 시간이 걸리는 알고리듬이다. 알고리듬이 단순하며 메모리가 원래 배열에 교체(Swap)을 위한 임시 변수를 제외하면 추가적으로 필요하지 않아 메모리가 제한적인 경우에 사용시 이점이 존재합니다. 선택 정렬 알고리듬 순서:   1. 주어진 배열 중에 최소값을 찾는다.   2. 그 값을 맨 앞에 위치한 값과 교체한다.   3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. (1, 2번 반복) 주어진 배열 중 최소값을 찾기 위한 Loop와 각각의 값의 자리를 비교하기 위한 Loop가 필요해 이중 루프를 사용합니다.이 과정이 i가 배열의 끝에 도달할 때까지, 즉 바깥쪽 Loop가 끝날 때..