자바 정렬

혀니·2024년 7월 1일

LG U+ 유레카 백엔드 과정

목록 보기

4/17

정렬

Item[] itemArray = {
new Item(3, "666"), new Item(2, "777"), new Item(5,"444"), new Item(3, "111")
};

1. implements Comparable

// 정렬이 되기 위한 방법 1: Comparable interface 구현
    static class Item implements Comparable<Item> {
        int itemId;
        String itemNm;

        Item(int itemId, String itemNm){
            this.itemId=itemId;
            this.itemNm = itemNm;
        }

        @Override
        public String toString(){
            return "Item [itemId=" + itemId + ", itemNm=" +itemNm+"]";
        }

        @Override
        public int compareTo(Item o) {
            // this 객체하고 아이템 o 기준으로 어떻게 정렬?

            //return this.itemId - o.itemId; // itemId asc : 앞에꺼에서 뒤에꺼 빼기
            // desc은 반대로 부호 붙이면 됨

            //return this.itemNm.compareTo(o.itemNm); //itemNm 기준

            //itemId 우선 비교, 같으면 itemNm 비교
            return this.itemId == o.itemId ? this.itemNm.compareTo(o.itemNm) : this.itemId - o.itemId;

        }
    }

2. Comparator 객체 익명 전달

// Comparator interface 객체 전달
        // 정렬하기 위한 방법2: Comparator 객체 전달(익명) // 대상 객체에 Comparable 구현 없어도 된다.
        Arrays.sort(itemArray, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                //return o1.itemId - o2.itemId;
                return o1.itemNm.compareTo(o2.itemNm); // 문자니까 compareTo
            }
        });

        // 정렬하기 위한 방법3: Comparator 객체 전달(Lamda) // 대상 객체에 Comparable 구현 없어도 된다.
        // 람다식: 매개변수 -> 리턴값
        // 오름차순 o1 o2 -> o1 - o2 / 내림차순 o1 o2 -> o2 - o1
        Arrays.sort(itemArray, (o1, o2) -> o1.itemId - o2.itemId);

        System.out.println(Arrays.toString(itemArray));
    }

3. Comparator 객체 람다식 전달

// 정렬하기 위한 방법3: Comparator 객체 전달(Lamda) // 대상 객체에 Comparable 구현 없어도 된다.
        // 람다식: 매개변수 -> 리턴값
        // 오름차순 o1 o2 -> o1 - o2 / 내림차순 o1 o2 -> o2 - o1
        Arrays.sort(itemArray, (o1, o2) -> o1.itemId - o2.itemId);

package _240621;

import java.lang.reflect.Array;
import java.util.*;

public class ArraySortTest {

    public static void main(String[] args) {
        List<Item> list = new ArrayList<>();
        list.add(new Item(3, "666"));
        list.add(new Item(2, "777"));
        list.add(new Item(5, "444"));
        list.add(new Item(3, "111"));

        System.out.println(list);
        Collections.sort(list, (el1, el2) -> el1.itemId - el2.itemId);
        Collections.sort(list, (el1, el2) -> el1.itemNm.compareTo(el2.itemNm));


//        int[] intArray = { 3, 5, 2, 7, 9, 4};
//        Arrays.sort(intArray);
//        System.out.println(Arrays.toString(intArray));

        String[] strArray={"Hello", "ABC", "WORLD", "UPLUS"};
        Arrays.sort(strArray, Collections.reverseOrder());
        System.out.println(Arrays.toString(strArray));

        Item[] itemArray = {
                new Item(3, "666"), new Item(2, "777"), new Item(5,"444"), new Item(3, "111")
        };


        // implements Comparable
        // 정렬 방법 1
        // Arrays.sort(itemArray);

        // Comparator interface 객체 전달
        // 정렬하기 위한 방법2: Comparator 객체 전달(익명) // 대상 객체에 Comparable 구현 없어도 된다.
        Arrays.sort(itemArray, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                //return o1.itemId - o2.itemId;
                return o1.itemNm.compareTo(o2.itemNm); // 문자니까 compareTo
            }
        });

        // 정렬하기 위한 방법3: Comparator 객체 전달(Lamda) // 대상 객체에 Comparable 구현 없어도 된다.
        // 람다식: 매개변수 -> 리턴값
        // 오름차순 o1 o2 -> o1 - o2 / 내림차순 o1 o2 -> o2 - o1
        Arrays.sort(itemArray, (o1, o2) -> o1.itemId - o2.itemId);

        System.out.println(Arrays.toString(itemArray));
    }

    // 정렬이 되기 위한 방법 1: Comparable interface 구현
    static class Item implements Comparable<Item> {
        int itemId;
        String itemNm;

        Item(int itemId, String itemNm){
            this.itemId=itemId;
            this.itemNm = itemNm;
        }

        @Override
        public String toString(){
            return "Item [itemId=" + itemId + ", itemNm=" +itemNm+"]";
        }

        @Override
        public int compareTo(Item o) {
            // this 객체하고 아이템 o 기준으로 어떻게 정렬?

            //return this.itemId - o.itemId; // itemId asc : 앞에꺼에서 뒤에꺼 빼기
            // desc은 반대로 부호 붙이면 됨

            //return this.itemNm.compareTo(o.itemNm); //itemNm 기준

            //itemId 우선 비교, 같으면 itemNm 비교
            return this.itemId == o.itemId ? this.itemNm.compareTo(o.itemNm) : this.itemId - o.itemId;

        }
    }
}

StackOverFlow 에러

메모리 - 스택메모리
메인 - 스택메모리

메인메소드를 위한 스택메모리
m1메소드의 스택메모리
-> 스택메모리가 반복되서 오버가 나서 Error가 남(스택오버플로우)

static void m1(){
        System.out.println("m1"+m1_cnt++); // static 변수는 공유된다.

        m1();
    }

정렬

선택정렬

삽입정렬

데이터가 거의 정렬 되어 있을 때 선택정렬보다 효율적
그 앞까지의 데이터는 정렬되어있다고 가정하여 두번째 데이터부터 정렬 시작
삽입될 데이터보다 작은 데이터를 만나면 멈춤 (오름차순 )
시간 복잡도는 O(N^2) 최악의 경우에도 O(N^2)
정렬이 거의 되어있는 상황에서 최선의 경우 O(N)으로 퀵 정렬보다 빠름

퀵정렬

기준을 설정한 다음 큰 수와 작은 수를 교환 후 리스트를 반으로 나눔
피벗이 사용됨 ( 피벗: 교환하기 위한 기준)
리스트를 분할하는 방법에 따라 여러 방법으로 나뉨
평균 시간 복잡도 O(N log N)
최악의 경우 O(N^2)
-> 데이터가 무작위로 입력되면 빠르게 동작함
-> 가장 왼쪽 데이터를 피벗으로 삼을 때, 데이터가 이미 정렬되어 있을 때 느리게 동작(삽입 정렬과 반대)