Tugas 3

MACAM – MACAM PENGURUTAN DATA

1. Bubble sort
Bubble sort adalah salah satu pengurutan metode
exchanging yang bersifat langsung dan termasuk jenis
pengurutan yang paling sederhana. Nama bubble sort
ini berasal dari sifat elemen terbesar yang selalu naik
ke atas (ke akhir dari list) seperti bubble.

Ide dari bubble sort adalah sebagai berikut :
· Algoritma dimulai dari elemen paling awal.
· 2 buah elemen pertama dari listdibandingkan.Jika elemen pertama lebih besar dari elemen kedua,dilakukan pertukaran.
· Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga, seterusnya sampai ke ujung elemen
· Bila sudah sampai ke ujung dilakukan lagi ke awal sampai tidak ada terjadi lagi pertukaran elemen.
· Bila tidak ada pertukaran elemen lagi, maka list elemen sudah terurut.

2. Quick Sort
Quick sort merupakan divide and conquer algorithm.
Algoritma ini mengambil salah satu elemen secara
acak (biasanya dari tengah) lalu menyimpan semua
elemen yang lebih kecil di sebelah kirinya dan semua
elemen yang lebih besar di sebelah kanannya. Hal ini
dilakukan secara rekursif terhadap elemen di sebelah
kiri dan kanannya sampai semua elemen sudah terurut.
Algoritma ini termasuk algoritma yang cukup baik dan
cepat. Hal penting dalam algoritma ini adalah
pemilihan nilai tengah yang baik sehingga tidak
memperlambat proses sorting secara keseluruhan.

Ide dari algoritma ini adalah sebagai berikut :
· Pilih satu elemen secara acak
· Pindahka semua elemen yang lebih kecil ke sebelah elemen tersebut dan semua elemen yang lebih besar ke sebelah kanannya. Elemen yang nilainya sama bisa disimpan di salah satunya. Ini disebut operasi partisi
· Lakukan sort secara rekursif terhadap sublist sebelah kiri dan kanannya.


3. Shell Short
· Metode Pertambahan Menurun
· Dikembangkan oleh Donald L. Shell (1959)
· Mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan


Contoh Program Sederhana Array :

#include

class Foo
{
public:
Foo() {} // default ctor
virtual ~Foo() {} // dtor
Foo( const Foo& ) {} // copy ctor
operator = ( const Foo& ) {} // assignment op
};

int main(int argc, char *argv[])
{
std::vector arrFoo;

Foo f1,f2,f3;
arrFoo.push_back(f1);
arrFoo.push_back(f2);
arrFoo.push_back(f3);
cout << "Size arrFoo: " << arrFoo.size();
arrFoo.pop_back();
cout << "Size arrFoo: " << arrFoo.size();
system( "PAUSE" );
return 0;
}