[알고리즘] 정렬

[알고리즘] 정렬

: 정렬(Sorting)이란 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것.

알고리즘 학습의 필수이고 대표적으로 버블, 선택, 삽입이 있다. 

# 버블정렬

: 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

배열의 전체를 순회하면서 앞, 뒤의 데이터를 비교후 Collections.swap으로 자리를 바꿔준다.

swap 여부를 체크하며 없을 경우 더 이상 비교할 필요가 없다고 간주하여 해당 루프를 종료한다.

[버블정렬] - 구현 예시코드

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort 
{
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) 
	{
        for (int i = 0; i < dataList.size() - 1; i++) 
			{
            boolean swap = false;
            
            for (int k = 0; k < dataList.size() - 1 - i; k++) 
			{
                if (dataList.get(k) > dataList.get(k + 1)) 
				{
                    Collections.swap(dataList, k, k + 1);
                    swap = true;
                }
            }
            
            if (swap == false) break;
        }
        
        return dataList;
    }
}

 

# 선택정렬

: 주어진 데이터 중, 최소값을 찾을 찾고 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.

이러한 방식으로 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

[선택정렬] - 구현 예시코드

import java.util.ArrayList;
import java.util.Collections;

public class SelectionSort 
{
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) 
	{
		// 인덱스 번호
        int lowest; 
        for (int i = 0; i < dataList.size() - 1; i++) 
		{
			// 검색하는 인덱스를 최소로 잡아두고 값을 비교하며 최소값을 저장
            lowest = i;
            for (int k = i + 1; i < dataList.size(); k++) 
			{
                if (dataList.get(lowest) > dataList.get(k)) 
				{
                    lowest = k;
                }
            }
            Collections.swap(dataList, lowest, stand);
        }
        return dataList;
    }
}

 

# 삽입정렬

: 두 번째 인덱스부터 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사하고 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동시킨다.

[삽입정렬] - 구현 예시코드

import java.util.ArrayList;
import java.util.Collections;

public class InsertionSort 
{
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) 
	  {
        for (int i = 0; i < dataList.size() - 1; i++) 
			{
            for (int k = i + 1; k > 0; k--) 
				{
                if (dataList.get(k) < dataList.get(k - 1)) 
				{
                    Collections.swap(dataList, k, k - 1);
                } 
				else 
				{
                    break;
                }
            }
        }
        return dataList;
    }
}

 

 

 

급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다 :)