[ java ] 정렬 알고리즘 > java

본문 바로가기
사이트 내 전체검색

java

[ java ] 정렬 알고리즘

페이지 정보

작성자 웹지기 댓글 0건 조회 2,091회 작성일 20-12-16 09:26

본문

버블 정렬(Bubble Sort)

 - 치환할 내용이 발생 하면 바로 치환

 ① 다른 정렬에 비해 속도가 느리다.

 ② 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교

 ③ 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교

 ④ 이를 전체배열의 크기 현재까지 순환하는 바퀴 수 만큼 반복

import java.util.Arrays;


public class Exam01_버블정렬 {

    public static void main(String[] args) {

        //버블 정렬

        int[] arr = {10, 9, 8, 7, 5};

        

        //오름차순으로 정렬

        for(int j=arr.length-1; j>0; j--) {

            for(int i=0; i<j; i++) {

                if(arr[i] > arr[i+1]) { //큰수를 오른쪽으로 보내면서 저장

                    int temp = arr[i];

                    arr[i] = arr[i+1];

                    arr[i+1] = temp;

                }

                //정렬 과정 확인

                System.out.println(Arrays.toString(arr));

            }

            System.out.println();

        }

        

        for(int i : arr) {

            System.out.print(i+"\t");

        }

        System.out.println();

        

        //내림차순으로 정렬

        for(int j=arr.length-1; j>0; j--) {

            for(int i=0; i<j; i++) {

                if(arr[i] < arr[i+1]) { //작은수를 오른쪽으로 보내면서 저장

                    int temp = arr[i];

                    arr[i] = arr[i+1];

                    arr[i+1] = temp;

                }

                //정렬 과정 확인

                System.out.println(Arrays.toString(arr));

            }

            System.out.println();

        }

        

        for(int i : arr) {

            System.out.print(i+"\t");

        }

    }

}

 

삽입 정렬(Insertion Sort)

 - 현재위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬

 ① 삽입 정렬은 두번째 인덱스부터 시작. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.

 ② 별도로 저장해 둔 삽입을 위한 변수와 빅 인덱스의 배열 값을 비교

 ③ 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고 비교 인덱스를 -1하여 비교를 반복

 ④ 만약 삽입 변수가 더 크면 비교 인덱스+1에 삽입 변수를 저장

 

선택 정렬(Selection Sort)

 - 현재 위치에 들어갈 값을 찾아 정렬하는 배열 - idx값만을 찾아놔서 나중에 치환

 ① 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

    (정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)

 ② 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.

 ③ 다음 인덱스에서 위 과정을 반복

import java.util.Arrays;

import java.util.Random;


public class Exam05_선택정렬2 {

    public static void main(String[] args) {

        Random r = new Random();

        

        int[] arr = new int[10];

        for(int i=0; i<arr.length; i++) {

            arr[i] = r.nextInt(20)+1;

        }

        System.out.println(Arrays.toString(arr));

        System.out.println();

        

        for(int j=0; j<arr.length; j++) {

            int minIdx = j;

            for(int i=j+1; i<arr.length; i++) {

                //가장작은 index 찾기

                if(arr[minIdx] > arr[i]) {

                    minIdx = i;

                }

                System.out.println(Arrays.toString(arr));

            }

            //idx의 값만을 가져와서 치환을한다.

            int temp = arr[j];

            arr[j] = arr[minIdx];

            arr[minIdx] = temp;

            System.out.println();

        }

        

        System.out.println(Arrays.toString(arr));

    }

}

 

합병 정렬(Merge Sort)

 - 분할 정복(Divide and conquer)방식으로 설계된 알고리즘. 

 - 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복

 - 분할 과정

  ① 현재 배열을 반으로 쪼갬. 배열의 시작 위치과, 종료 위치를 입력받아 둘을 더한 수 2를 나눠 그 위치를 기준으로 나눈다.

  ② 이를 쪼객 배열의 크키가 0이거나 1일 때 까지 반복한다.

 - 합변 과정

  ① 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정

  ② i 에는 A배열의 시작 인덱스를 저장. j에는 B 배열의 시작 주소를 저장

  ③ A[i]와 B[i]를 비교. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장

     A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i값을 하나 증가

  ④ 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달 할 때까지 반복

  ⑤ 끝까지 저장을 못한 배열의 값을, 순서대로 전부C에 저장

  ⑥ C 배열을 원래의 배열에 저장

 

추천0 비추천0

댓글목록

등록된 댓글이 없습니다.

Total 113건 6 페이지
  • 38 [ java ] 리컨값이 없는 메소드 만들기
  • return 을 사용하지 않고 바로 출력을 해버린다. 이때 return에 해당하는 값에 void를 넣어준다. public static int getDivisor ==&gt; public static void getDivisor public class Exam04_getDivisor { public static void main(String[] args) { getDivisor(10); getDivisor(10); ...
  • 웹지기 12-17 1991 0 0 댓글 0
  • 37 [ java ] 두수 중 큰수를 확인하는 메소드 만들기
  • 코드 작성 public class Exam02_Method { public static void main(String[] args) { int num1 = 10; int num2 = 24; int result = LargeNumbers(num1, num2); System.out.println("큰수 확인 : "+result); } //두개의 정수중 큰수를 반환하는 Lar...
  • 웹지기 12-17 3102 0 0 댓글 1
  • 36 [ java ] 메소드 (method)
  • 메소드(method) - 객체의 행위를 표현하기 위한 행위 - 반복적으로 사용되는 코드를 줄위기 위한 행위 - 특정작업을 수행하기 위한 명령문의 집합 public class Exam01_method { public static void main(String[] arg) { int r = addNumber(10, 54, '+'); System.out.println(r); } // public -&gt;...
  • 웹지기 12-17 1884 0 0 댓글 1
  • 35 [ java ] ArrayList 객체를 이용한 노래 등록 프로그램 작성하기
  • MusicPlayList클래스는 musicList 라는 이름으로 ArrayList 객체를 생성하여 musicList에 노래 제목을 추가하고 삭제하는 프로그램 MusicPlayList 클래스 구성은 아래와 같다. 메뉴 - [1]노래 추가 [2]노래 삭제 [3]종료 &gt;&gt; [1]노래추가 시 노래가 없으면 - 재생목록이 없습니다 출력 메뉴 - [1]마지막에 추가 [2]원하는 위치에 추가 &gt;&gt; [1]마지막에 추가 선택시 메뉴 - 추...
  • 웹지기 12-16 4660 0 0 댓글 0
  • 34 [ java ] Collection
  • Collection 1) 요소(element) 라고 불리는 가변 개수의 객체들의 모음 - 데이터 - 객체들의 컨테이너라고도 불림 - 요소의 개수에 따라 collection 은 자동 크기조절 - collation 은 요소의 삽입, 삭제에 따른 자리 이동에 용이 2) 고정크기의 배열을 다루는 어려움 해소 3) 다양한 객체들의 삽입, 삭제, 검색등을 관리하기 용이 ArrayList&lt;String&gt; Collection의 내부 구성 ArrayList&#...
  • 웹지기 12-16 2171 0 0 댓글 0
  • 33 [ java ] 검색 알고르즘
  • Sequential sesarch - 가장 단순한 검색 방법으로 원소의 정렬이 필요없다. 하지만 리스트의 길이가 길어진다. - 처음부터 순차적으로 검색하는 알고리즘 import java.util.Arrays; import java.util.Arrays; public class Exam07_Sequential_search { public static void main(String[] args) { int[] arr = {13, 35, 15...
  • 웹지기 12-16 1617 0 0 댓글 0
  • 열람중 [ java ] 정렬 알고리즘
  • 버블 정렬(Bubble Sort) - 치환할 내용이 발생 하면 바로 치환 ① 다른 정렬에 비해 속도가 느리다. ② 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교 ③ 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교 ④ 이를 전체배열의 크기 현재까지 순환하는 바퀴 수 만큼 반복 import java.util.Arrays; public class Exam01_버블정렬 { public sta...
  • 웹지기 12-16 2092 0 0 댓글 0
  • 31 [ java ] 학생별 과목점수 입력 및 통계 프로그램 작성하기 (학생은 최대 5명, 과목은 3과목)
  • 1) 학생별 과목 점수 입력 - 과목은 총 3과목 ( DataBase, Python, Java ) 2) 학생총 입력 가능 수 - 5명 3) 학생을 검색 - 학생의 평균과 학점 표기 4) 점수별 - 학생별 점수를 별로 표기 5) 과목별 평균점수, 전체과목의 평균점수 시작화면 ==========성적관리프로그램========== [1]성적입력 [2]개별확인 [3]전체확인 [4]성적통계 [5]종료 &gt;&gt; [1] 화면 -...
  • 웹지기 12-16 8788 0 0 댓글 0
  • 26 [ java ] 정보처리 기사의 합격여부를 알려주는 프로그램 작성
  • 정보처리기사의 합격여부를 알려주는 프로그램을 작성하시오 합격기준 : 정보처리기사는 5개 과목이 있으며 한과목당 문제는 20문제 이며 총합이 60개가 넘어야 합격이다. 단, 총합이 60개가 넘어가더라도 한과목이라도 8개 미만의 개수를 맞았다면 탈락이다. import java.util.Scanner; public class Question3_2 { public static void main(String[] args) { //합격기준 :...
  • 웹지기 12-15 2071 0 0 댓글 0
  • 25 [ java ] 마트 계산대 프로그램, 10000원짜리 구매시 지불해야하는 금액
  • 마트 계산대 프로그램입니다. 10000원짜리 추석선물셋트를 구입했을 때 지불해야하는 금액을 계산해주는 프로그램을 작성하시오. 단, 11개 이상 구매시에는 10% 할인이 적용됩니다. import java.util.Scanner; public class Question3_1 { public static void main(String[] args) { //10000원짜리 구입 //11개 이상 구입시 10%할인 Scan...
  • 웹지기 12-15 3592 0 0 댓글 0
  • 24 [ java ] 거스름돈을 입력 받아 내줘야하는 지폐와 동전의 개수를 출력
  • 거스름돈을 입력 받아 내줘야하는 지폐와 동전의 개수를 출력 단, 최대단위는 10000원, 최소단위는 100원 import java.util.Scanner; public class Question2_2 { public static void main(String[] args) { //거스름돈 입력 받아 내줘야 하는 지폐와 동전의 개수를 출력하는 프로그램 작성 //최대 단위는 10000원 최소 단위 100 Scanne...
  • 웹지기 12-15 4711 0 0 댓글 0
게시물 검색

회원로그인

접속자집계

오늘
2,944
어제
8,701
최대
61,067
전체
11,207,236

그누보드5
Copyright © funyphp.com. All rights reserved.