정렬 알고리즘 - 오름차순

숫자를 다루다보면 원하는대로 정렬을 하고 싶은 마음이 생긴다.

	int[] arr = new int[5];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = random.nextInt(10);
		}

 

다섯칸의 정수 배열의 각 인덱스에 랜덤한 숫자를 초기화했다.

이를 정렬해보는 알고리즘에 관해 이야기해보고자 한다.

​

1) 오름차순

: 헷갈려 하는 경우가 잦아 추가 기술하면

: 오름차순은 오르는 순서이다. 1->2->3->4->5 를 떠올리면 된다.

​

오름차순으로 상기의 코드를 오름차순으로 정렬해보자.

 

for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i]<arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}

 

처음 공부할때는 temp 의 역할을 야바위를 떠올리며 익혔었다.

3개의 컵에 공이 2개 들어있는 상황을 떠올렸는데, 굳이 돌려서 이해할 필요가 없지 싶다.

야바위나 고리옮기기등은 이미지를 처음 잡는데 사용하고 인덱스 자체를 떠올리면 좀 더 쉽다.

​

그림으로 나타내면 이렇다.

​

​

매우 난잡한 그림이라 죄송하다.

그래도 직관적인 표현이라 전달이 되길 바란다.

​

나의 사고의 흐름은 이러하다.

1. for문의 제어로 i가 j보다 숫자가 크다.

1-1. i인덱스가 가장 마지막인덱스의 숫자를 담고있다.

2. 오름차순을 목표하므로 arr[i]가 더 커야한다.

3. if문으로 arr[j]가 더 큰경우를 조정해야 한다.

4. arr[j]를 arr[i]로 옮길것이다.

5. arr[j]를 temp로 뺀다.

6. arr[i]에 있는걸 이제 비어있는 arr[j]에 넣는다.

7. arr[i]에 이제 temp에 있는 더 큰값을 넣는다.

​

이를 반복한다.

​

안익숙하다보니 이런과정으로 생각을하고 손짓을하며 상상의 나래를 펼치기도 한다. 나중에는 좀 더 자연스럽게 되길.

​

지금의 방식을 사용하면 오름차순으로 정렬을 할 수 있다.

하지만 부족하다는 생각이 들지않는가?

​

바로 중복이 제거되지 않아서 그럴 것이다.

​

중복을 제거하기위한 구문을 추가하겠다.

개인적으로 혹시 보시는 분이 계시다면, 보기전에 생각해보고 보시길 권한다.

 

for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i]==arr[j]) {
					arr[i] = random.nextInt(10);
					i--;
				}
				if(arr[i]<arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}

 

중복일때 새로 값을 생성하고 다시 중복여부를 탐색하도록 했다.

개인적으로 처음 알고리즘을 접할때 정말 천재가 아니라면 머리속에서 그 로직을 그리기에 시간이 소요되는 것 같다.

​

직접 생각해보시는걸 권하며, 참고하실 수 있도록 그림을 참고할테니 읽어보시는 분들은 코드를 보기전에 생각해보시고 보시길 바란다.

​

라고 쓰고 그림을 그려보았으나 심각한 그림실력으로 오히려 방해하게 될거같아 글로 나타내보려 한다.

​

위에 적은것 처럼 의식의 흐름대로 적을테니 도움이 되길 바란다.

​

생각이 복잡해질때는 샘플링( Sampling )을 하는 것이 효율적이다.

​

i가 2일때를 가정해보자,

i가 2이라면 현재로서 값이있는 가장 마지막 인덱스는 arr[2]이고,

arr[0], arr[1]와 중복되지 않아야 한다.

​

그래서 첫번째 for문에서 비교할 값인 arr[2]의 인덱스를 지정하고,

그 안의 for문에서 0,1을

(j = 0 ; j<i ; j++)에서 비교하도록 반복시키게 된다.

​

그렇게 값이 같은 것이 있다면, arr[2]은 다시 랜덤값을 지정시키고,

i--; 를 통해 다시 값을 내렸다가

이번에는 i를 관리하는 for문의 i++를 통해 원래의 값으로 복원된다.

​

즉, i는 다시 처음부터 비교할 수 있게 된다.

중복이 발생하지 않는다면 다음 단계로 넘어갈 수 있게되는 것이다.

​

이러한 방법으로 오름차순으로 정수를 정렬하는 방법을 확인해보았다.

​

기초적인 정렬을 마쳤으니 ( 내림차순은 방향만 다르다. )

정렬에 관련한 다른 알고리즘에 대한 공부를 하고 포스팅하도록 하겠다.

​

공부한 내용에 대해 혼자 고민하고 복습하며 정리하는 것으로, 부족하거나 잘못된 내용이 있다면 말씀부탁드립니다. 감사합니다.