Published 2023. 1. 15. 23:23

정렬 알고리즘 - 1

lecture

728x90

오늘은 버블 정렬(Bubble sort) , 선택정렬(Selection sort)와 삽입정렬(Insertion sort) 에 대해서 알아보도록하겠습니다.

정렬은 데이터의 탐색의 최적화를 만들기 위해 순서대로 나열해주는 기능입니다.

프로그래밍 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생합니다 이를 얼마나 효과적으로 해결할 수 있는 지가 정렬의 핵심입니다.

또한, 이진 탐색이라는 강력한 알고리즘을 사용하기 위해선 데이터의 정렬은 필수입니다.

버블 정렬은 굳이 요즘에 쓰이지 않는다고 합니다, 그 이유는 직관적으로는 이해가 쉬운 정렬로 구현하기 쉽지만 일반적으로 O(n^2) 의 시간복잡도를 갖기 때문에 실전에서는 거의 사용할 일이 없습니다.

하지만, 버블정렬에서 사용되는 Swap 연산이 중요하기 때문에 '초기 프로그래밍시' 자주 사용되는 예제 중 하나 입니다.

버블 정렬 -

인접한 두 원소를 비교하며, 큰 수를 계속하여 뒤로 보내 정렬하는 방식을 사용(오름 차순으로 정렬하는 경우)하는 정렬 방식이다.

~~->원소들이 거품이 올라오는 것처럼 보여 거품 정렬(Bubble Sort)이라고 이름지었다~~

버블 정렬의 이해

->어떤 대상을 '오름차순'으로 정렬할 때 버블 정렬은 원소를 처음부터 탐색하면서, 큰 수를 계속하여 뒤로 밀어내는 방식을 사용한다. 예를 들어 [5, 3, 1, 10, 7]이라는 배열을 버블 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다.

기본적인 자바 예시 )

public ArrayList<Integer> sort(ArrayList<Integer>dataList){
		for(int index = 0; index<dataList.size()-1; index++) {
			boolean swap = false;

			for(int index2=0; index2<dataList.size()-1-index; index2++) {
				if(dataList.get(index2)>dataList.get(index2+1)) {
					Collections.swap(dataList, index2, index2+1);
					swap= true;
				}
			}
			if(swap==false) {
				break;
			}
		}
		return dataList;

	}

2번째 선택정렬(Selection sort) 입니다.

선택 정렬이란?

한번의 배열 탐색에서 가장 작은 원소의 위치를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 방식을 사용하는 정렬 방식입니다.

예를 들어) 어떠한 대상을 오름차순 으로 정렬할 때 선택 정렬은 첫번째 부터 탐색을 하면서 작은 수를 찾고 그 수를 배열의 앞쪽으로 보내는 방식을 사용합니다.

	public class SelectionSort{
		public ArrayList<Integer> sort(ArrayList<Integer>dataList){

			int lowest;
			for(int stand = 0; stand<dataList.size()-1; stand++) {
				lowest = stand;
				for(int index = stand+1; index<dataList.size(); index++) {
					if(dataList.get(lowest)>dataList.get(index)) {
						lowest = index;
					}
				}
				Collections.swap(dataList, lowest, stand);
			}
			return dataList;
		}
	}

3번째 삽입정렬(Insertion Sort)입니다

삽입정렬이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

매 순서마다 해당 원소를 삽입할 수 있는위치를 찾아 해당 위치에 넣는다.

개념적으로 접근을 하자면 -

삽입 정렬은 두번째 자료부터 시작하여 그 앞의 자료들과 비교하여 (왼쪽 자료) 비교하여 삽입할 위치를 지정한 후 자료들 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.

public class insertsort {

	public ArrayList<Integer> sort(ArrayList<Integer>dataList) {
		for(int index=0; index<dataList.size()-1; index++) {
			for(int index2=index+1; index2>0; index2--) {
				if(dataList.get(index2)<dataList.get(index2-1)) {
					Collections.swap(dataList, index2, index2-1);
				}else {
					break;
				}
			}
		}
		return dataList;
		
	}
	public static void main(String[] args) {
		ArrayList<Integer>testData = new ArrayList<Integer>();
		for(int index =0; index<100; index++) {
			testData.add((int)(Math.random()*100));
		}
		insertsort isort = new insertsort();
	
		isort.sort(testData);
		System.out.println(testData);
		
		
	}
	
}

삽입 정렬의 특징

안정한 정렬방법과 레코드의 수가 적을 경우 알고리즘 자체가 매애ㅜ 간단하므로 다른 복잡한 정렬방법 보다 유리할수 있다.

대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적입니다.

단점은 비교적 많은 레코드들의 이동을 포함합니다. 또한 수가 많고 레코드 크기가 클 경우에 적합하지 않습니다.

시간복잡도의 최선의 경우

비교횟수 - 이동없이 1번의 비교로 이루어진다
외부루프: (n-1) 번
Best T(n) = O(n)

최악의 경우(입력 자료가 역순일 경우)

비교 횟수

외부 루프 안의 각 반복마다 i번의 비교 수행
외부 루프(n-1)+(n-2)+.............n(n-1)/2=O(n^2)

교환횟수

외부 루프의 각 단계마다(i+2)번의 이동 발생
n(n-1)/2+2(n-1)=(n^2+3n-4)/2 =O(n^2)

Worst T(n) = O(n^2)