Algorithm/Sorting

카운팅 정렬 (Counting Sort)

카운팅 정렬 - 입력되는 값을 값이자 인덱스로 보고 새로운 카운팅 배열에 추가를 하며 개수를 기반으로 정렬하는 알고리즘 - 비교를 하지 않기 때문에 숫자의 범위가 작을때 빠르고 효율적으로 정렬할 수 있는 알고리즘 - 숫자의 개수는 적은데 값의 범위가 커진다면 비효율적인 알고리즘 - 카운팅 배열이라는 새로운 배열과 출력값을 저장할 새로운 배열 2개가 더 생성되기 때문에 다른 정렬 알고리즘에 비해서 메모리를 더욱 많이 사용함 정렬 알고리즘 Step 1. Counting Array Step 2. Counting Array Summing Step 3. Sorting 1. 값을 받은 다음 max + 1 의 길이에 해당하는 counting 배열을 만듦 2. counting 배열에는 기존 배열의 값을 인덱스로 보고 ..

삽입 정렬 (Insertion Sort)

삽입 정렬 - 손 안의 카드를 정리하는 방법과 유사한 정렬 방법 - 새로운 카드를 발견하면 그간 눈에 본 앞의 카드들을 보고 맞는 자리에 넣어 준다. - 두번째 자리부터 시작해서 앞쪽의 원소와 비교하여 올바른 자리에 넣는 알고리즘 - 최선의 경우가 O(N)이라는 좋은 효율을 가지고 있기 때문에 다른 정렬 알고리즘에 사용되기도 한다. 정렬 알고리즘 (오름차순) 1. 두 번째 자리에 있는 원소를 key 원소로 선택한다. 2. key 원소 앞에 있는 원소와 하나씩 비교하면서 key 값 보다 큰 원소들은 하나씩 뒤로 밀어준다. 3. key 보다 작은 원소를 발견하면 그 바로 뒤 자리에 key 원소를 넣어준다. 4. 앞의 배열들은 오름차순으로 배열되있다는 것이 확정적이기 때문에 위와 같은 방법을 쓸 수 있다. 5..

선택 정렬 (Selection Sort)

선택 정렬 - 이름 말 그대로 자리를 선택하고 해당 자리에 들어올 값을 찾아서 넣어주는 정렬 - 버블 정렬과 헷갈릴 수 있으니 조심 - 버블 정렬과 다른 것은 먼저 자리를 선정한다는 점 정렬 알고리즘 (오름차순) 1. 배열의 자리를 선정한다. (보통 0번째부터 순서대로) 2. 0번째 자리에 들어갈 값의 인덱스을 찾는다. (오름차순 기준 최솟값) 3. 배열을 쭉 돌면서 찾았으면 이제 자리를 바꾼다. 4. n 차례 반복했으면 앞의 n 개에는 순서대로 알맞는 값이 쌓이게 된다. 5. 따라서 배열을 쭉 순회하면서 최소값을 찾을때는 n+1 부터 찾으면 된다. 6. 반복. JAVA Code import java.io.BufferedReader; import java.io.IOException; import java..

버블 정렬 (Bubble Sort)

버블 정렬 - Selection Sort와 유사한 알고리즘으로 인접한 두 원소의 대소를 비교해서 정렬하는 알고리즘이다. - 정렬을 하게 되면 오름차순 기준으로 맨 마지막 배열에 가장 큰 값이 순서대로 쌓이게 된다. - 원소의 이동이 거품이 수면위로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 정렬 알고리즘 (오름차순) 1. 배열의 0번째에서 시작하게 되는데 0번부터 마지막까지 비교를 한차례 시작한다. 2. 비교를 하면서 만약 앞의 원소가 뒤의 원소보다 크다면 바꿔주고 다시 인덱스를 한칸 넘어가서 비교를 한다. 3. 비교를 마치고 나면 맨 마지막 위치에 가장 큰 값이 위치하게 된다. 4. 이러한 비교를 배열번 만큼 반복하는데 마지막 자리에는 반복한 횟수만큼 큰 값들의 자리가 고정 되기 때문에 i ..