정렬 알고리즘(버블,단순선택,단순삽입)

- 중복 없는 리스트, 중복있는 리스트 정렬

-버블 정렬

-단순 선택 정렬

-단순 삽입 정렬

• 사실 ArrayList의 sort기능이 있지만 공부를 위해 만들어봤습니다.

---

• 중복 되는 숫자가 없도록 리스트를 만들어줍니다

1. 랜덤 값을 받습니다. (int randnum)
2. 받은 랜덤값과 리스트에 들어간 값중에 중복된 값이 있는지 확인합니다.(중복값이 없다면4번)
3. 있다면 다시 새로운 랜덤값을 넣습니다.(2번으로 돌아가기)
4. 없다면 값을 넣습니다.
5. 반복합니다.

 Random random = new Random();
    //중복되는 숫자가 없도록 만들어주기
    // int NumericRange는 랜덤 수의 범위를 정해준다
    public ArrayList<Integer> NoDuplicateList(int ListLength , int NumericRange){
        ArrayList<Integer> randomIntList = new ArrayList<Integer>();
        boolean tf , checkboolean = false, same =true;

        // 중복되는 숫자가 없도록 짜주자
        for(int i=0; i< ListLength; i++){
            tf = true;
            if(i==0){
                randomIntList.add(random.nextInt(NumericRange));
            }else {
                // 중복성 검사  중복 값이 있으면 다시 주입
                int randnum;
                while (tf) {
                    randnum = random.nextInt(NumericRange);
                    // System.out.println("try Input Number : "+randnum);
                    //중복성 검사 부분
                    for (Integer integer : randomIntList) {
                        //System.out.println("already numberList: "+integer.intValue());
                        if (randnum == integer) {
                            // 같은 값이 있다면 당장 break; 시키고 다시 값 넣어주기
                            same = false;
                            break;
                        }
                        same =true;
                    }
                    if(same){
                        randomIntList.add(randnum);
                        tf = false;
                        break;
                    }
                }
            }
        }
        return randomIntList;
    }

---

• 중복 숫자가 있는 리스트 입니다.

Random random = new Random();
//중복이 있는 리스트
    public ArrayList<Integer> duplicatesList(int length, int NumericRange){
        ArrayList<Integer> arrayList = new ArrayList<Integer>();

        for ( int i =0; i < length; i++) {
            arrayList.add(randomNum(NumericRange));
        }

---

정렬(sorting)

• 정렬이란

  핵심 항목(나이, 길이 등의 핵심 항목)의 대소관계에 따라 데이터 집합을
  일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다.

  오름차순

• 키값이 작은 데이터 순으로, 올라가는 그림

  내림차순

• 내려가는 그림, 가장높은 값 순으로 나오는 경우
  
  

버블 정렬

(찾아보니 시작점이 head부분이나 끝부분 이렇게 두가지로 나뉘는 데, 큰 차이는 없다.)

• 첫번째 패스가 끝나면 마지막 인덱스는 정렬이 끝난 더이상 비교하지 않아도 되는 인덱스 입니다.
• 마지막 부분의 인덱스는 정렬이 끝났으니 비교하지않아도 괜찮습니다 (배열의 길이 - n회)

---

• 나는 시작부분부터 정렬하는 코드를 짜봤다.

    public ArrayList<Integer> bubbleSort(ArrayList<Integer> arrayList){
        int repetitionNum = 0;
        for (int t: arrayList){
            for(int i=0; i < arrayList.size()-repetitionNum;i++){
                if(i+1 == arrayList.size()-repetitionNum){

                }else {
                    if(arrayList.get(i) > arrayList.get(i+1)){
                        int tmp = arrayList.get(i);
                        arrayList.set(i, arrayList.get(i+1));
                        arrayList.set(i+1, tmp);
                    }

                }

            }
            repetitionNum++;
        }

        return arrayList;
    }

1. ArrayList를 받는다.
2. 리스트의 길이만큼 반복한다. (foreach문)
3. 비교 대상은 반복한 횟수만큼 준다 [n=반복횟수 , List.size() - n]
4. 비교후 작은 값을 앞 인덱스로 바꿔준다
5. 반복 정렬

---

결과

(오름차순)

---

단순 선택 정렬

---

---

• 이름 그대로 단순하게 가장 작은 값을 선택해서 정렬을 시작합니다.

  (n = 0 : 배열의 길이)

  1. 해당 정렬을 순차검색을 통해 가장 작은 값을 찾아내서 n번째 인덱스로 보낸다.
  2. n++

public  ArrayList<Integer> straightselectionSort(ArrayList<Integer> arrayList ){

        // 타겟 인덱스는 처음부터
        int targetIndex =0;
        int minimum = arrayList.get(0); //인덱스 첫번째부터
        int minumumIndex = 0;

        for (int i:arrayList) {

            minimum = arrayList.get(targetIndex);


            // 먼저 가장 작은 값을 구함
            for(int j=targetIndex; j<arrayList.size(); j++){
                if(minimum > arrayList.get(j)){
                    minimum = arrayList.get(j);
                    minumumIndex = j;

                }
            }
            if(targetIndex > arrayList.size()){
                // 교환작업,
                int tmp = arrayList.get(targetIndex);
                arrayList.set(targetIndex, minimum);
                arrayList.set(minumumIndex, tmp);
            }

            targetIndex++;
        }

        return arrayList;
    }

---

결과

• 앞서 구현한 버블정렬과 같은 값을 나타내는 것을 볼수있다! (오름차순)

---

단순 삽입 정렬

• 말 그대로 target이 되는 부분부터 index 요소 순서대로 하나하나 비교해나가면서
  대소관계에 따라 작은 값을 왼쪽으로 밀어내 삽입하는 알고리즘
• 즉 해당 요소 하나를 왼쪽으로 하나씩 비교해가며 자기자신보다 작은 값이 나올때까지 앞부분으로 삽입하는 정렬입니다.
  

public ArrayList<Integer> straightInsertionSort(ArrayList<Integer> arrayList){

        int targetIndexNum = 0;

        for(int i=0; i < arrayList.size();i++){

            if(targetIndexNum==0){
                targetIndexNum++;
            }else {
                int temp = arrayList.get(targetIndexNum);
                for(int j =1; j < i; j++){
                    // target index
                    if(targetIndexNum-j < 0){
                        break;
                    }
                    // 타겟 인덱스의 값이 더 작으면 왼쪽으로 교환해줘야함
                    if(arrayList.get(targetIndexNum-j) > temp){
                        int chtemp = arrayList.get(targetIndexNum-j);
                        arrayList.set(targetIndexNum-j, temp);
                        arrayList.set(targetIndexNum, chtemp);
                    }else {
                        break;
                    }
                    targetIndexNum++;
                }
            }

        }
        return arrayList;
    }

---

결과

---

참고 : - 내손으로 직접 코딩하며 확인한다! 자료구조와 함께 배우는 알고리즘 입문(자바편) - 인터넷 참고