버블 정렬 (Bubble sort algorithm)
서론오늘은 버블 정렬 알고리즘 (bubble sort algorithm)를 알아볼 것이다.문제 푸는 아이디어숫자로 이루어진 배열을 오름차순 정렬한다고 해보자. 인접한 두개의 요소를 비교한다. i가 i+1 보다 크다면, i와 i+1 을 교체한다. 이를 첫번째 요소부터 n 까지 순회하고 나면, 가장 큰 숫자가 n 번째 자리에 놓일 것이다. 그리고 또 첫번째 요소부터 n까지 순회하면, 두번째로 큰 숫자가 n-1 번째 자리에 놓일 것이다. 이를 n번 반복하면, 모든 배열이 정렬되어 있을 것이다.[4,3,2,1] 배열을 예시로 들어보자.i=0, i=1 을 비교한다. i=0이 i=1 보다 크기 때문에, 둘을 교체한다. [3,4,2,1]i=1, i=2 을 비교한다. i=1이 i=2 보다 크기 때문에, 둘을 교체한다...
순열 정렬 알고리즘 (Permutation sort algorithm)
서론오늘부터 정렬 알고리즘을 공부해볼 것이다. 그 중에서 가장 기본적인 순열 정렬(Permutation Sort)를 먼저 학습하려고 한다. 가장 기본적이라고 언급한 이유는, brute-force 기반이기 때문이다. 모든 케이스를 다 나열해보고, 알맞는 하나를 찾아가는 알고리즘이다.문제 푸는 아이디어[3,2,1] 을 오름차순으로 정렬하려고 한다. 아주 무식한 방법(brute-force)로 정렬한다고 해보자. 그렇다면 3,2,1 이라는 3개의 원소를 가지고, 만들 수 있는 모든 케이스를 만들고, 각각의 케이스가 오름차순 정렬되어 있는지 확인하는 것이다. 이것이 brute-force 기반 정렬인, 순열 정렬이다. 정리하자면, 이 문제는 두가지 Step 으로 나뉜다.순열 생성정렬 여부 확인순열(順列) 이란?순열..