[JAVA] 배열 요소를 역순으로 정렬하는 알고리즘

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

배열의 요소가 1, 2, 3, 4, 5, 6, 7 이렇게 7개 있다고 하면 역순으로 정렬하면 7, 6, 5, 4, 3, 2, 1이다.

 

 

그림에서 보는 것과 같이 요소들을 서로 바꿔주면 된다.

요소들을 바꿔주려면 먼저 swap함수를 정의해야한다.

static void swap(int[] arr, int a, int b) //배열의 요소 값을 스왑
	{
		int temp;
		temp = arr[a];
		arr[a]= arr[b];
		arr[b] = temp;
	}

매개변수 a와 b에 교환할 배열의 인덱스를 받고, 인덱스 a의 값과 인덱스 b의 값을 바꾼다.(swap)

 

이 swap 메소드를 응용해서 요소를 역순으로 정렬하는 알고리즘을 구현할 수 있다.

static void reverseArray(int[] arr) //배열 요소를 역순으로 정렬
	{
		for(int i = 0; i < arr.length/2; ++i)
		{
			swap(arr, i, arr.length - i-1);
		}
	}

arr.length(배열의 길이)가 홀수여도 상관없다. arr.length가 7이라고 가정하면 arr.length / 2 는 3이기 때문이다.(i는 int형 타입이기 때문에 3.5가 아니다.)

(arr.length(배열의 길이)가 짝수면 당연히 상관없음)

0부터 arr.length까지 반복을 진행하고, swap 메소드의 매개값에 배열, i, arr.length -i -1을 넘겨준다.

왜 이러한 매개값을 넘기는지는 아래와 같다.

• 배열(arr) : 매개값으로 참조된 배열의 값을 정렬하기 위해
• i : 배열(arr)의 i번째 인덱스의 값과 arr.length- i -1번째 인덱스의 값을 바꾸기 위해
• arr.length -i -1 : 위와 동일

배열의 인덱스는 0부터 시작함을 염두하고 잘 생각해 보면 이해가 될 것이다.

 

위의 swap메소드와 reverseArray메소드를 합치면 아래와 같다.

static void reverseArray(int[] arr) //배열 요소를 역순으로 정렬
{
    for(int i = 0; i < arr.length/2; ++i)
    {
        int temp = arr[i];
        arr[i]= arr[arr.length - i-1];
        arr[arr.length - i-1] = temp;
    }
}

 

아래의 코드는 실행 예제이다.

public class Main{
	static void reverseArray(int[] arr) //배열 요소를 역순으로 정렬
	{
			
		for(int i = 0; i < arr.length/2; ++i)
		{
			int temp = arr[i];
			arr[i]= arr[arr.length - i-1];
			arr[arr.length - i-1] = temp;
		}
	}
	
	static void printArray(int[] array) //배열 요소 출력
	{
		for(int i = 0; i < array.length; ++i)
		{
			if(i == array.length-1) {System.out.println(array[i]); break;}
			System.out.print(array[i] + ", ");
		}
	}
	
	public static void main(String[] args) {
		int[] array = {1,2,3,4,5,6,7};
		printArray(array);
		reverseArray(array);
		printArray(array);
	}
}
/*
1, 2, 3, 4, 5, 6, 7
7, 6, 5, 4, 3, 2, 1
*/

 

좀 더 자세히 스왑과정을 보여주는 예제

public class Main{
	static void swap(int[] arr, int a, int b) //배열의 요소 값을 스왑
	{
		int temp;
		temp = arr[a];
		arr[a]= arr[b];
		arr[b] = temp;
		System.out.println("Index " + a + "와(과) " + b + "를 교환");
		printArray(arr);
	}
	
	static void reverseArray(int[] arr) //배열 요소를 역순으로 정렬
	{
		for(int i = 0; i < arr.length/2; ++i)
		{
			swap(arr, i, arr.length - i-1);
		}
	}
	
	static void printArray(int[] array) //배열 요소 출력
	{
		for(int i = 0; i < array.length; ++i)
		{
			if(i == array.length-1) {System.out.println(array[i]); break;}
			System.out.print(array[i] + ", ");
		}
	}
	
	public static void main(String[] args) {
		int[] array = {1,2,3,4,5,6,7};
		printArray(array);
		reverseArray(array);
		//printArray(array);
	}
}
/*
1, 2, 3, 4, 5, 6, 7
Index 0와(과) 6를 교환
7, 2, 3, 4, 5, 6, 1
Index 1와(과) 5를 교환
7, 6, 3, 4, 5, 2, 1
Index 2와(과) 4를 교환
7, 6, 5, 4, 3, 2, 1
*/​