이론 공부/알고리즘

[알고리즘] 선택 정렬 Selection Sort

설명 원소를 넣을 위치를 정하고,어떤 원소를 넣을지 선택한 후 선택한 원소를 지정한 자리에 넣는 알고리즘이다. 과정 (오름차순 정렬인 경우) 1. 배열의 원소 중에서 최소값을 찾는다. 2. 해당 값을 배열의 맨 앞에 위치한 값과 교환한다. 3. 고른 자리(맨 앞)를 제외한 나머지 배열을 같은 방식으로 반복한다. 구현(Java) public static void sort(int[]arr){ for (int i = 0; i arr[j]){ minIdx= j; } } //지정위치에 있는 ..

[알고리즘] 거품 정렬 Bubble Sort

설명 서로 인접한 두 원소의 대소를 비교하고, 조건(오름차순, 내림차순 등)에 맞지 않다면 자리를 교환하면서 정렬하는 알고리즘이다. Selection Sort와 유사하다. 과정 배열의 크기 : N (0~N-1) 1회전은 i=0 부터 i와 i+1번째 원소, 즉 자신과 자신의 오른쪽 수를 비교해서 조건에 맞지 않는다면 서로 교환한다. 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동해있으므로 다음 회전에서 마지막 원소는 제외된다. 2회전도 i=0부터 1번과 동일하게 수행한다. 그러면 두번째로 큰 수가 마지막에서 두번째에 위치한다. 3회전에서는 동일하게 수행해준다. 0~N-3까지만 확인하게 된다. ⇒ 1회전에서는 0개 제외 ⇒ 2회전에서는 1개 제외 ⇒ 3회전에서는 2개 제외 ⇒ N회전에서는 N-1개 제외 구현(..