Bubble sort
Vs Quick sort
Bago tayo
pumunta sa main event alamin muna natin ang bawat isang algorithm una Bubble
sort.
Isa sa
pinaka basic na sorting algorithm ang bubble sort? It is used in
practice and its main application is to make an introduction to the sorting
algorithms. Bubble sort belongs to O(n2) sorting
algorithms, which makes it quite inefficient for sorting large data volumes.
Bubble sort is stable and adaptive.
Isa sa pinaka basic na idea
about dito ay ginagamit ito sa pamamagitan ng pag kukumpara sa bawat laman ng
array isa-isa at pag katapos nito ay uulitin nito ang unang step kung saan mag
sisimula ulit cya sa umpisa hangang sa matapos nito ang sorting.
Code:
// Example Program in
C++
// to sort an array
// using bubble sort
#include<iostream.h>
void main(void)
{
int temp, i, j;
int ar[10];
cout<<"enter elements of
array:\n";
for(i=0; i<10; i++)
cin>>ar[i];
// sorting is done here
for(i=0;i<10;i++)
for(j=0; j<(10-1); j++)
if (ar[j]>ar[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
}
// till here
for(i=0; i<10; i++)
cout<<endl<<ar[i];
cout<<endl;
}
Try ninyong gumamit ng program nito at makikita mu sa pag
sisimulate mu ng mga code na isa isa nitong ikinukumpara ang laman ng bawat array hangang sa ito ay matapos. The best case of bubble sort
is the ascending order of the number dahil direct nitong nalalaman kung na sort
a ang mga laman ng array ngunit lahat ay may kahinaan and descending order ng
number ng array ay lubhang nakaka apekto sa pag sosort ng algorithm na ito kaya
lubhang mabagal ang pag sort nito kaysa sa ibang sorting algorithm.
Kung panu to
nanggyayari e2 ang mga larawan at example
Quick sort naman tayo
Ang quick sort algorithm ay isa sa
pinaka mabilis na algorithm. Quicksort is a relatively simple sorting
algorithm using the divide-and-conquer recursive procedure. It is the quickest
comparison-based sorting algorithm in practice with an average running time.
Mas madalas gamitin ang quick sort kaysa sa bubble sort kasi mas efficient ang quick sort algorithm dahil sa massive sorting nito.
panu nga ba gumagana ang quick sort?
Quicksort, like mergesort, is a divide-and-conquer recursive algorithm. The
basic divide-and-conquer process for sorting a subarray S[p..r] is summarized
in the following three easy steps:
Divide: Partition S[p..r] into two subarrays S[p..q-1] and S[q+1..r] such that
each element of S[p..q-1] is less than or equal to S[q], which is, in turn,
less than or equal to each element of S[q+1..r]. Compute the index q as part of
this partitioning procedure
Conquer: Sort the two
subarrays S[p...q-1] and S[q+1..r] by recursive calls to quicksort.
Combine: Since the
subarrays are sorted in place, no work is needed to combing them: the entire
array S is now sorted.
QUICKSORT(S, P, r)
1 If p < r
2 then q <- PARTITION(S, p, r)
3 QUICKSORT(S, p, q-1)
4 QUICKSORT(S, q+1, r)
note: to sort the whole array S, the initial
parameters would be: QUICKSORT(S, 1, length[A])
PARTITION(S, p, r)
1 x <- S[r]
2 i <- p-1
3 for j <- p to r-1
4 do if S[j] <= x
5 then i <- i+1
6 swap S[i] <-> S[j]
7 swap S[i+1] <-> S[r]
8 return i+1
Quicksort's running time depends on the result of
the partitioning routine - whether it's balanced or unbalanced. This is
determined by the pivot element used for partitioning. If the result of the
partition is unbalanced, quicksort can run as slowly as insertion sort; if it's
balanced, the algorithm runs asymptotically as fast as merge sort. That is why
picking the "best" pivot is a crucial design decision.
The Wrong Way: the popular way of choosing the pivot is to use the first element; this
is acceptable only if the input is random, but if the input is presorted, or in
the reverse order, then the first elements provides a bad, unbalanced,
partition. All the elements go either into S[p...q-1] or S[q+1..r]. If the
input is presorted and as the first element is chosen consistently throughout
the recursive calls, quicksort has taken quadratic time to do nothing at all.
The Safe Way: the
safe way to choose a pivot is to simply pick one randomly; it is unlikely that
a random pivot would consistently provide us with a bad partition throughout
the course of the sort.
Median-of-Three Way: best
case partitioning would occur if PARTITION produces two subproblems of almost
equal size - one of size [n/2] and the other of size [n/2]-1. In order to
achieve this partition, the pivot would have to be the median of the entire
input; unfortunately this is hard to calculate and would consume much of the
time, slowing down the algorithm considerably. A decent estimate can be
obtained by choosing three elements randomly and using the median of these
three as the pivot.
code:
#include <stdio.h>
#include <stdlib.h>
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int choose_pivot(int i,int j )
{
return((i+j) /2);
}
void quicksort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}
void printlist(int list[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
void main()
{
const int MAX_ELEMENTS = 10;
int list[MAX_ELEMENTS];
int i = 0;
// generate random numbers and fill them to the list
for(i = 0; i < MAX_ELEMENTS; i++ ){
list[i] = rand();
}
printf("The list before sorting is:\n");
printlist(list,MAX_ELEMENTS);
// sort the list using quicksort
quicksort(list,0,MAX_ELEMENTS-1);
// print the result
printf("The list after sorting using quicksort algorithm:\n");
printlist(list,MAX_ELEMENTS);
}
And the Result iS!!!
Quick Sort Algorithm Wins!!!!
- quick sort is better than the bubble sort because of possibility na ang set ng
array ay kadalasan ay hindi na ka sort agad kaya ang
suggestion ko ay mas
magandang gamitin ang quick sort.
-Adrian Paul Q. Liveta
-200910042
Reference:
http://www.algolist.net/Algorithms/Sorting/Bubble_sort
http://learning-computer-programming.blogspot.com/2007/06/sorting-array-using-bubble-sort.html
http://www.devx.com/vb2themax/Tip/18972
http://warp.povusers.org/grrr/bubblesort_eng.html
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/quickSort.htm
http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html
http://www.devx.com/vb2themax/Article/19900
http://warp.povusers.org/SortComparison/
http://www.cprogramming.com/tutorial/computersciencetheory/quicksort.html
