ALGORITMA PENGURUTAN

 Algoritma pengurutan internal yang utama antara lain :

• 1     Buble Sort
• 2.      Selection Sort
• 3.      Insertion Sort
• 4.      Shell Sort
• 5.      Merge Sort
• 6.      Radix Sort
• 7.      Quick Sort
• 8.      Heap Sort

Namun hanya akan di bahas 3 metode sort karena ketiga metode tersebut yang dianggap mudah, yaitu : Buble Sort, Selection Sort, Insertion Sort.

1)    1.  Buble Sort

       Proses pengurutan yang sederhana dengan prinsip gelembung, maksudnya gelembung air yang mengapung untuk data yang terurut menaik (ascending) maka elemen bernilai kecil akan diapungkan (ke indeks terkecil), artinya diangkat ke atas (indeks terkecil) melalui pertukaran. Bekerja dengan berulang kali membandingkan dua elemen data dan akan menukar elemen data yang urutannya salah. 


Contoh :
Pengurutan bilangan dari kecil ke besar
     
        5 4 2 1 3 
dari contoh diatas maka, program nanti akan mencari bilangan terkecil kemudian dibandingkan dan akhirnya bilangan terkecil tersebut nantinya diletakkan disebelah kiri, menjadi :
        2 5 4 1 3  
        1 5 4 2 3   
kemudian program akan mengerjakan pada indexs ke 2 dan itu akan dilakukan  terus menerus hal yang sama seperti diatas hingga bilangan terkecil nanti berada di ujung sebelah kiri dan yang bilangan terbesar berada di ujung sebelah kanan.

• Jika akan melakukan buble short menurun, maka program akan mencari bilangan terkecil terlebih dahulu, kemudian dibandingkan.
• Jika akan melakukan buble short menaik, maka program akan mencari bilangan terbesar terlebih dahulu, baru setelah itu membandingkannya.

Algoritma Buble Short secara Ascending 

         Kamus Data :

         i, j, temp : integer

         Algoritma

         for ( i = 0 ; i <= ( N-2) ; i++)

              for ( j = (N-1) ; j >= (i+1) ; j--)

                   if ( A[j-1] > A[j])

                     temp <- A[j-1]

                     A[j-1] <- A[j]

                     A[j] <- temp

                   endif

              endfor

          endfor

          endprocedure

Program Algoritma Buble Short dengan Bahasa C

{ int L[5] ;

   int i, N ;

  //proses untuk memasukkan data array

 printf ("Banyak data : ") ; 

 scanf (" %i ", &N);

 for ( i=0; i<N; i++)

 { printf ("Data ke-%i : ", i+1);

    scanf (" %i ", &L[i]);  } //end loop i

 //memanggil procedure buble short

 //proses menampilkan kembali data array

   printf ("\n Data array terurut \n");

   for ( i=0; i<N ; i++)

 { printf ( " %3i ", L[i] ); };

  getche ();

  } //end program

 { int a, b, temp;

  //proses sortir dengan buble short

  for ( a=0; a <= (N-2); a++ )

  { for ("b = (N-1); b >= (a+1); b--)

     { if ( A [b-1] > A[b] ;

        { temp = A[b-1];

           A[b-1] = A[b];

           A[b] = temp; }  //endif

         }   //end loop j

      }     //end loop if

   }    //end procedure




2. Selection Short

            Algoritma selection short memiih elemen maksimum / minimum pada array, kemudian menempatkan elemen tersebut pada awal atau akhir tergantung pada urutannya ascending / descending. Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Jika array berukuran N, maka jumlah pass adalah ( N-1 ).

            Terdapat 2 pendekatan dalam metode pengurutan dengan selection short, yaitu :

• Algoritma pengurutan maksimum ( maximum selection short) yaitu memilih elemen maksimum sebagai basis pengurutan
• Algoritma pengurutan minimum ( minimum selection short ) yaitu memilih elemen minimum sebagai basis pengurutan

1. Maximum Selection Short Ascending

Untuk mendapatkan array yang terurut menaik, setiap pass pengurutan terdapat proses mencari harga maksimum dan proses pertukaran dua buah elemen array. Misal terdapat array L dengan N =5 buah elemen yang belum terurut, array akan diurutkan secara ascending dengan algoritma maximum selection short.

9

7

12

6

1

Pass 1:

• Cari elemen maksimum di dalam array L[0..4]. Maks L[2]=12
• Tukar maks dengan L[4], diperoleh

9

7

1

6

12

            Pass 2:

• Berdasarkan urutan array pada pass 1, cari elemen maks di dalam array L[0..3]. Maks L[0]=9
• Tukar maks dengan L[3], diperoleh

6

7

1

9

12

Pass 3:

·        Berdasarkan array pada pass2, cari elemen maks didalam array L[0..2]. Maks L[1]=7

·        Tukar maks dengan L[2], diperoleh

6

1

7

9

12

            Pass 4:

·        Berdasarkan array pada pass 3, cari elemen maks didalam array L[0..1]. Maks L[0]=6

·        Tukar maks dengan L[1], diperoleh

1

6

7

9

12

            Selesai array L sudah terurut secara ascending.

Algoritma Maximum Selection Short secara Ascending:

KAMUS

maks,k,j,temp : integer

ALGORITMA

For (k=(N-1) ;k>=0 ; k<-k-1)

maks<-0

//cari elemen maks

For (j=0 ; j<=k : j<-j+1)

If (A[j] > A[maks])

maks<-j;

endif

endfor

v_Tukar (A[k] ,A[maks] )    //panggil procedure v_Tukar

endfor

endprocedure

Algoritma Maximum Selection Short Ascending Bahasa C:

main()

{          int L[5];

             Int i,N;

//input data array

            Printf(“banyak data : ”);

            Scanf(“%i”, &N);

            For(i=0 ; i<N ; i++)

            {          printf(“data ke-%i : ”, i+1);

                        Scanf(“%i”, &L[i]);     } //end loop 1

            getche();

}

void v_SelaAsc(Int A[5], int N)

{          int maks,k,j,temp;

            For(k=N-1); k>=0; k--)

            {maks=0 ;

              For (j=0; j<=k; j++)

               { if (A[j] >A[maks])

                 {maks=j; } //endif

               }  //end loop j

                 v_Tukar (&A[k] , &A[maks]);

            } //end loop k

} //endprocedure v_SelAsc

void  v_Tukar (int *P, int *M)

{          int temp;

            temp= *P;

            *P= *M;

            *M=temp;

} //end procedure v_Tukar

2. Maximum Selection Short Descending

9

8

11

7

12

Pass 1:

• Cari elemen maks didalam array L[0..4]. Maks=L[4]=12
• Tukar maks dengan L[0], diperoleh

12

8

11

7

9

Pass 2:

• Berdasarkan susunan array pass 1, cari elemen maks didalam array L[1..4]. Maks=L[2]=11
• Tukar maks dengan L[1], diperoleh

12

11

8

7

9

Pass 3:

• Berdasarkan susunan array pass 2, cari elemen maks didalam array L[2..4]. Maks=L[[4]=9
• Tukar maks dengan L[2], diperoleh

12

11

9

7

8

Pass 4:

• Berdasarkan susunan array pass3, cari elemen maks didalam array L[3..4]. Maks=L[4]=8
• Tukar maks dengan L[3], diperoleh

12

11

9

8

7

Selesai, array L sudah terurut secara descending (menurun).

Algoritma Maximum Selection Short secara Descending:

KAMUS:

k,maks,j,temp : integer

ALGORITMA

for(k=0; k<=(N-2); k<-k+1)

 //cari elemen maksimum

   maks<-k

   for(j=k+1; j<=(N-1); j<-j+1)

      if(A[j] > A[maks])

            maks<-j

      endif

   endfor

   temp <- A[k]

   A[k] <- A[maks]

   A[maks] <- temp

endfor

Algoritma Maximum Selection Short secara Descending Bahasa C:

#include <stdio.h>;

#include <conio.h>;

void  v_Tukar (int *P, int *M);

void v_SelDsc(Int A[5], int N);

main()

{          int L[5];

            int I,k,j,maks,temp,N;

            printf(“banyak data : ”);

            scanf(“%i”, &N);

            //input data array

printf(“input data array\n”);

for(i=0; i<N; i++)

{          printf(“data ke-%i =  ”, i+1);

            scanf(“%i”, &L[i]); //end loop i

            //panggil procedure v_SelDesc

v_SelDesc (L,N);

printf(“\noutput data array terurut: \n”);

for(i=0; i<N; i++)

{          printf(“%5i”, L[i]); } //end loop i

printf(“\ntekan enter…\n”);

getche();

}          //end main program

void v_SelDsc(Int A[5], int N)

{          int k,maks,j,temp;

            //proses sorting maks descending

            for(k=0; k<=(N-2); k++)

            {          //cari elemen maksimum

                        maks=k;

                        for(j=(k+1); j<=(N-1); j++)

                        {          if (A[j] > A[maks])

                                    maks=j ; } //endfor loop j

                        v_Tukar (&A[k] , &A[maks]);

            } //endfor loop k

} //endprocedure v_SelDesc

void  v_Tukar (int *P, int *M)

{          int temp;

            temp= *P;

            *P= *M;

            *M=temp;

} //end procedure v_Tukar

#include <conio.h>;

void v_minDesc(Int A[5], int N);

void  v_Tukar (int *P, int *M);

main()

{          int L[5];

            int i, N;

//input data array

            printf(“input data array\n ”);

            printf(“\nbanyak data : “);

            scanf(“%i”, &N);

            for(i=0 ; i<N ; i++)

            {          printf(“data ke-%i : ”, i+1);

                        scanf(“%i”, &L[i]);      } //end loop i

                        //panggil procedure v_minDesc

                        v_minDesc (L,N);

                        //output data array

                        printf(“\n data sortir: \n”);

                       

for(i=0; i<N; i++)

                        {          printf(“%5i”, L[i]); }  //end loop 1

                                    printf(“\n tekan enter \n”);

            getche();

}          //end main program

void v_minDesc(Int A[5], int N)

{          int min,k,j,temp;

            for(k=(N-1); k>=1; k--)

            {min=0 ;

              for (j=0; j<=k;  j++)

               { if (A[j] >A[min])

                 {min=j; } //end loop j

                 v_Tukar (&A[k] , &A[min]);

            } //end loop k

} //end procedure  v_minDesc

void  v_Tukar (int *P, int *M)

{          int temp;

            temp= *P;

            *P= *M;

            *M = temp;

} //end procedure v_Tukar

1.      Minimum Selection Short Ascending

Untuk mendapatkan array yang terurut menaik, setiap pass pengurutan terdapat proses mencari harga minimum dan proses pertukaran dua buah elemen array. Misal terdapat array L dengan N =5 buah elemen yang belum terurut, array akan diurutkan secara ascending dengan algoritma minimum selection short.

9

7

12

6

1

Pass 1:

• Cari elemen minimum di dalam array L[0..4]. Min L[4]=1
• Tukar min dengan L[0], diperoleh

1

7

12

6

9

            Pass 2:

• Berdasarkan urutan array pada pass 1, cari elemen min di dalam array L[1..4]. Min L[3]=6
• Tukar min dengan L[1], diperoleh

1

6

12

7

9

Pass 3:

·        Berdasarkan array pada pass2, cari elemen min didalam array L[2..4]. Min L[3]=7

·        Tukar min dengan L[2], diperoleh

1

6

7

12

9

            Pass 4:

·        Berdasarkan array pada pass 3, cari elemen min didalam array L[3..4]. Min L[4]=9

·        Tukar min dengan L[3], diperoleh

1

6

7

9

12

            Selesai, array L sudah terurut secara ascending.

Algoritma Minimum Selection Short secara Ascending:

KAMUS

min,k,j,temp : integer

ALGORITMA

For (k=0; k<=(N-2); k<-k+1)

maks<-0

//cari elemen min

For (j=(k+1); j<=(N-1); j<-j+1)

If (A[j] > A[min])

min<-j;

endif

endfor

v_Tukar (A[k] ,A[min] )   

endfor

Algoritma Minimum Selection Short Ascending Bahasa C:

#include <stdio.h>;

#include <conio.h>;

void v_minAsc(Int A[5], int N);

void  v_Tukar (int *P, int *M);

main()

{          int L[5];

             Int i,j,k,min,temp,N;

//input data array

            printf(“input data array\n ”);

            printf(“\nbanyak data : “);

            scanf(“%i”, &N);

            for(i=0 ; i<N ; i++)

            {          printf(“data ke-%i : ”, i+1);

                        scanf(“%i”, &L[i]);      } //end loop i

                        //panggil procedure v_minAsc

                        v_minAsc (L,N);

                        //output data array

                        printf(“\n data sortir: \n”);

                        for(i=0; i<N; i++)

                        {          printf(“%5i”, L[i]); }  //end loop 1

                        printf(“\n tekan enter \n”);

            getche();

}          //end main program

void v_minAsc(Int A[5], int N)

{          int min,k,j,temp;

            for(k=0; k<=(N-2); k++)

            {min=k ;

              for (j=(k+1); j<=(N-1); j++)

               { if (A[j] >A[min])

                 {min=j; } //end loop j

                 v_Tukar (&A[k] , &A[min]);

            } //end loop k

} //end procedure

void  v_Tukar (int *P, int *M)

{          int temp;

            temp= *P;

            *P= *M;

} //end procedure v_Tukar

2.      Minimum Selection Short Descending

9

8

11

7

12

Pass 1:

• Cari elemen min didalam array L[0..4]. Min=L[3]=7
• Tukar min dengan L[4], diperoleh

9

8

11

12

7

Pass 2:

• Berdasarkan array pass 1,cari elemen min dalam array L[0..3].Min=L[1]=8
• Tukar min dengan L[3], diperoleh

9

12

11

8

7

Pass 3:

• Berdasarkan array pass 2, cari elemen min didalam array L[0..2]. Min=L[0]=9
• Tukar min dengan L[2], diperoleh

11

12

9

8

7

Pass 4:

• Berdasarkan array pass3, cari elemen min didalam array L[0..1]. Min=L[0]=11
• Tukar min dengan L[1], diperoleh

12

11

9

8

7

Selesai, array L sudah terurut secara descending (menurun).

Algoritma Minimum Selection Short secara Descending:

KAMUS:

k,min,j,temp : integer

ALGORITMA

for(k=(N-1); k>=1; k<-k-1)

   min<-0

//cari nilai terkecil

   for(j=0; j<=k;  j<-j+1)

      if(A[j] > A[min])

            min<-j

      endif

   endfor

           v_Tukar (A[k] , A[min]);

   endfor

Algoritma Minimum Selection Short secara Descending Bahasa C:

#include <stdio.h>;

#include <conio.h>;

void v_minDesc(Int A[5], int N);

void  v_Tukar (int *P, int *M);

main()

{          int L[5];

            int i, N;

//input data array

            printf(“input data array\n ”);

            printf(“\nbanyak data : “);

            scanf(“%i”, &N);

            for(i=0 ; i<N ; i++)

            {          printf(“data ke-%i : ”, i+1);

                        scanf(“%i”, &L[i]);      } //end loop i

                        //panggil procedure v_minDesc

                        v_minDesc (L,N);

                        //output data array

                        printf(“\n data sortir: \n”)            

for(i=0; i<N; i++)

                        {          printf(“%5i”, L[i]); }  //end loop 1

                                    printf(“\n tekan enter \n”);

            getche();

}          //end main program

void v_minDesc(Int A[5], int N)

{          int min,k,j,temp;

            for(k=(N-1); k>=1; k--)

            {min=0 ;

              for (j=0; j<=k;  j++)

               { if (A[j] >A[min])

                 {min=j; } //end loop j

                 v_Tukar (&A[k] , &A[min]);

            } //end loop k

} //end procedure  v_minDesc

void  v_Tukar (int *P, int *M)

{          int temp;

            temp= *P;

            *P= *M;

            *M = temp;

} //end procedure v_Tukar