Materi kuliah 09 sort part 4
0 likes98 views
The document describes the insertion sort algorithm, which sorts a list of numbers by taking each number and inserting it into the sorted position by shifting greater numbers to the right. It provides an example of sorting the list 95, 34, 32, 25, 75, 42, 22 step-by-step using insertion sort. The document also includes C++ code to implement insertion sort on an array of random numbers.
![#include <iostream.h>
#include <conio.h>
void insertion_sort(int data[])
{
int temp, j;
for(int i=1; i<10; i++)
{
temp = data[i];
j = i-1;
while(temp < data[j] && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
void main()
{
int data[10]={5,34,32,25,75,42,22,2,9,1};
insertion_sort(data);
for (int i=0;i<10;i++)
cout<<"data["<<i<<"]= : "<<data[i]<<endl;
getch();
}](https://image.slidesharecdn.com/materikuliah09-sortpart4-130611094237-phpapp01/85/Materi-kuliah-09-sort-part-4-11-320.jpg)
Materi kuliah 09 sort part 4
- 1. Oleh Drs KH.BUDI YONO
- 2. Insertion Sort Metode Insertion Sort mirip dengan cara mengurutkan kartu, kartu diambil selembar demi selembar dan disisipkan (insert) pada posisi seharusnya. Proses pengurutan dimulai dari data ke 2 sampai data terakhir. Data akan dibandingkan dengan posisi sebelumnya dan disisipkan pada posisi yang sesuai. Pada proses penyisipan data, maka data-data yang lain akan bergeser ke belakang (kanan).
- 3. Insertion Sort Misalkan kita memiliki data acak sebagai berikut : 95, 34, 32, 25, 75, 42, 22
- 4. Insertion Sort Data sebelumnya : 95, 34, 32, 25, 75, 42, 22 Langkah 1, Temp = 34 J = 0 Temp < 95? YA Data Ke 1 = 95 95, 95, 32, 25, 75, 42, 22 J = -1 STOP Hasil : Data ke J+1 (0) = Temp (34) 34, 95, 32, 25, 75, 42, 22
- 5. Insertion Sort Data sebelumnya : 34, 95, 32, 25, 75, 42, 22 Langkah 2, Temp = 32 J = 1 Temp < 95? YA Data ke 2 = 95 34, 95, 95, 25, 75, 42, 22 J = 0 Temp < 34? YA Data ke 1 = 34 34, 34, 95, 25, 75, 42, 22 J = -1 STOP Hasil : Data ke J+1 (0) = Temp (32) 32, 34, 95, 25, 75, 42, 22
- 6. Insertion Sort Data sebelumnya : 32, 34, 95, 25, 75, 42, 22 Langkah 3, Temp = 25 J = 2 Temp < 95? YA Data ke 3 = 95 32, 34, 95, 95, 75, 42, 22 J = 1 Temp < 34? YA Data ke 2 = 34 32, 34, 34, 95, 75, 42, 22 J = 0 Temp < 32? YA Data ke 1 = 32 32, 32, 34, 95, 75, 42, 22 J = -1 STOP Hasil : Data ke J+1 (0) = Temp (25) 25, 32, 34, 95, 75, 42, 22
- 7. Insertion Sort Data sebelumnya : 25, 32, 34, 95, 75, 42, 22 Langkah 4, Temp = 75 J = 3 Temp < 95? YA Data ke 4 = 95 25, 32, 34, 95, 95, 42, 22 J = 2 Temp < 34? TIDAK STOP Hasil : Data ke J+1 (3) = Temp (75) 25, 32, 34, 75, 95, 42, 22
- 8. Insertion Sort Data sebelumnya : 25, 32, 34, 75, 95, 42, 22 Langkah 5, Temp = 42 J = 4 Temp < 95? YA Data ke 5 = 95 25, 32, 34, 75, 95, 95, 22 J = 3 Temp < 75? YA Data ke 4 = 75 25, 32, 34, 75, 75, 95, 22 J = 2 Temp < 34? TIDAK STOP Hasil : Data ke J+1 (3) = Temp (42) 25, 32, 34, 42, 75, 95, 22
- 9. Insertion Sort Data sebelumnya : 25, 32, 34, 42, 75, 95, 22 Langkah 6, Temp = 22 J = 5 Temp < 95? YA Data ke 6 = 95 25, 32, 34, 42, 75, 95, 95 J = 4 Temp < 75? YA Data ke 5 = 75 25, 32, 34, 42, 75, 75, 95 J = 3 Temp < 42? YA Data ke 4 = 42 25, 32, 34, 42, 42, 75, 95 J = 2 Temp < 34? YA Data ke 3 = 34 25, 32, 34, 34, 42, 75, 95 J = 1 Temp < 32? YA Data ke 2 = 32 25, 32, 32, 34, 42, 75, 95 J = 0 Temp < 25? YA Data ke 1 = 25 25, 25, 32, 34, 42, 75, 95 J = -1 STOP Hasil : Data ke J+1 (0) = Temp (22) 22, 25, 32, 34, 42, 75, 95
- 10. Insertion Sort Data Awal : 22, 25, 32, 34, 42, 75, 95 Data Akhir :
- 11. #include <iostream.h> #include <conio.h> void insertion_sort(int data[]) { int temp, j; for(int i=1; i<10; i++) { temp = data[i]; j = i-1; while(temp < data[j] && j>=0) { data[j+1] = data[j]; j--; } data[j+1] = temp; } } void main() { int data[10]={5,34,32,25,75,42,22,2,9,1}; insertion_sort(data); for (int i=0;i<10;i++) cout<<"data["<<i<<"]= : "<<data[i]<<endl; getch(); }