곽로그

개념 n번째 인덱스를 선택한다. 그런다음 인덱스 n-1부터 인덱스 0까지 역순으로 순회하여 n번째 인덱스 값과 비교한다. n번째 인덱스 값보다 비교하는 인덱스(k)의 값이 크면, 비교하는 인덱스(k)를 인덱스 k+1로 옮긴다. 만약 인덱스(k)의 값이 작으면 인덱스 k+1자리에 인덱스 n을 삽입한다. 구현 기준값은 인덱스가 1부터 시작하고 리스트의 길이-1까지 순회한다. 기준값에 대한 비교값은 인덱스가 기준인덱스-1 부터 시작해서 0까지 역순으로 순회한다. 비교값이 기준값보다 크면 비교 인덱스+1에 비교값을 넣는다. 그러다 비교값이 기준값보다 작으면 while문을 빠져나오고 비교인덱스+1에 temp값을 넣는다. 삽입 정렬에서 핵심은 비교인덱스 +1 에 어떤 값을 넣느냐 인 것 같다. 기준값보다 비교값이 ..

개념 "최솟값을 선택"하는 알고리즘이다. 버블정렬은 좌우-좌우를 순차적으로 비교하면서 각 턴마다 최대값을 맨 오른쪽으로 보내는 것이라면, 선택알고리즘은 각 턴마다 최소값을 찾은 후 맨 왼쪽으로 보내는 알고리즘이다. 구현 7 5 6 9 2 를 예로 들어보자. 첫번째 순회에서는 인덱스 0에 넣을 최솟값을 찾는다. 7 5 6 9 2 중 최솟값은 2 이므로 인덱스 0에 있는 7과 자리를 바꾼다. 첫번째 순회의 결과는 2 5 6 9 7이 된다. 첫번째 순회에서 인덱스 0은 최소값으로 정렬되었다. 두번째 순회에서는 인덱스 1에 넣을 최솟값을 찾는다. (2) 5 6 9 7에서 최솟값은 5 이므로 인덱스 1에 5를 넣는다. 두번째 순회의 결과는 2 5 6 9 7 이되고 인덱스 0,1은 크기순으로 정렬되어 있다. 이런식..

왜 이름이 거품정렬일까? 프로그래밍에서 변수나 메서드의 이름을 지을때는 그 역할을 명확하게 표현하게끔 짓는다고 했다. 근데 이 정렬은 왜 버블(거품)정렬일까. 나 같은 사람이 한명은 아닐 것 같아서 구글링을 했다. "배열에서 요소의 이동이 물에서 거품의 움직임과 비슷하기 때문이다"라고한다. 그러니까 큰 거품이 제일 먼저 올라가는 것 처럼 가장 큰 요소가 가장 먼저 정렬이 된다. 이런 뜻인 것 같은데 글쎄. 개념 가장 큰 거품이 가장 먼저 올라간다는 이반 무쉬케티크(?)아저씨의 말처럼 버블정렬은 가장 큰 요소(반대로 가장 작은 요소가 먼저 일 수도 있다) 가 가장 먼저 정렬이 되는 알고리즘이다. 즉 오름차순(혹은 내림차순)으로 정렬을 한다는 내용이다. 오름차순을 구현하는 방법은 간단하다. 이웃하는 두 개의..