알고리즘 - 정렬

참조: https://chb2005.tistory.com/75

프로그래머스 - 최댓값 만들기1

정수 배열 numbers가 매개변수로 주어집니다. numbers의 원소 중 두 개를 곱해 만들 수 있는 최댓값을 return하도록 solution 함수를 완성해주세요.

public class Solution {
	public int solution(int[] numbers) {
    	int answer = 0;
        int temp = 0;
        
        for(int i = 0; i < numbers.length - 1; i++) {
        	for(int j = 0; j < numbers.length - 1 - i; j++) {
            	if(numbers[j] > numbers[j+1]) {
                	temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
                }
            }
        }
        answer = numbers[numbers.length - 1] * numbers[numbers.length - 2];     
        return answer;
    }
}    
        

for문 하나로 돌려서 정렬이 한 번 밖에 안됐는데, for문 두 개 돌리면 된다.

두 번째 for문에서 j < numbers.length -1 -i까지 반복하는 이유가 궁금했는데, 처음에 정렬할 때 제일 큰 수가 맨 뒤에 정렬되므로 다음 정렬 시에는 확인해줄 필요가 없기 때문에 길이를 하나 씩 줄어들게 하는 것이였다.

버블 정렬(Bubble Sort)

• 순서대로 근접한 두 수를 비교해서 오른쪽 수가 왼쪽 수보다 더 작으면 교환한다.
• 이 작업을 한 번 수행할 때마다 맨 뒤에 가장 큰 수가 가게 된다.
• 이 작업을 최대 n - 1번 반복하면 정렬이 완료 된다.
  - 시간 복잡도: O(n^2)

for(int i = 0; i < n - 1; i++) {
	for(int j = 0; j < n - 1 - i; j++) {
    	if(arr[j] > arr[j+1]){
     		int temp = arr[j];
            arr[j] = arr[j+1};
            arr[j+1] = temp;
        }
    }