8 Replies - 1075 Views - Last Post: 14 January 2011 - 07:13 AM Rate Topic: -----

#1 ahsanalishahid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 35
  • Joined: 20-October 10

Arrays Bubble sort

Posted 13 January 2011 - 01:02 PM

Hello all! :D

I have made this bubble sort program. And i want to know if I had made any mistake.(Although its working fine. Just curious that i have used bubble sort algo incorrectly).

Tips and help appreciated :)


#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
int main()
{
	const int size = 16;
	int ar[size]={90,80,70,65,54,44,32,505,100,33,-12,-1,0,-900,88,75};
	unsigned int temp = 0;  // to swap array values

	cout << "Unsorted Array: " << endl;
	for(int j=0; j <size;j++)
	{
		cout << setw(6) << ar[j];
	}
	
	cout << endl;

	for(int s=0; s<size-1;s++)
	{
		for(int k=0;k<size;k++)
		{
			if(k == (size-1)) 
			{
				break;
			}
			else if(ar[k] > ar[k+1])
			{
				temp = ar[k];
				ar[k] = ar[k+1];
				ar[k+1]  = temp;
			}
		}
	}

	
	cout << "Sorted array is: " << endl;
	for (int m=0;m<size;m++)
	{
		cout << setw(6) << ar[m];
	}









_getche();
}


Is This A Good Question/Topic? 0
  • +

Replies To: Arrays Bubble sort

#2 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Arrays Bubble sort

Posted 13 January 2011 - 01:19 PM

You could start your second for loop at 1 instead of 0.

Then put it all into a function.
Was This Post Helpful? 0
  • +
  • -

#3 ahsanalishahid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 35
  • Joined: 20-October 10

Re: Arrays Bubble sort

Posted 13 January 2011 - 01:36 PM

Thanks for help :)
Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Arrays Bubble sort

Posted 13 January 2011 - 01:57 PM

This part of your code:
    for (int k=0; k<size; k++)
    {
        if (k == (size-1))
        {
            break;
        }


has the same effect as this:
    for (int k=0; k<size-1; k++)
    {


except that your way does an extra, unnecessary comparison on every iteration.

Also, your program goes all the way through the array from beginning to end on every iteration, which means that it keeps pointlessly re-examining (i.e. comparing) all of the elements that have already been sorted, over and over again.

Bear in mind that after the first iteration, the last element is the biggest (and it will remain so thereafter), and after the second iteration ,the next-to-last element is the 2nd biggest (and it will remain so thereafter), and so on. Therefore there is no reason to look at those elements ever again, so you should "shorten" the array from the top down on each succeeding iteration, thus minimizing the number of comparisons.

Like this:
    for (int s=size-1; s>0; s--)
    {
        for (int k=0; k<s; k++)
        {
            if (ar[k] > ar[k+1])
            {
                temp = ar[k];
                ar[k] = ar[k+1];
                ar[k+1]  = temp;
            }
        }
    }



Bubble-sort is inherently an inefficient algorithm, but that's no reason to make it even less efficient.
Was This Post Helpful? 1
  • +
  • -

#5 ahsanalishahid  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 35
  • Joined: 20-October 10

Re: Arrays Bubble sort

Posted 13 January 2011 - 02:17 PM

View Postr.stiltskin, on 13 January 2011 - 12:57 PM, said:

This part of your code:
    for (int k=0; k<size; k++)
    {
        if (k == (size-1))
        {
            break;
        }


has the same effect as this:
    for (int k=0; k<size-1; k++)
    {


except that your way does an extra, unnecessary comparison on every iteration.

Also, your program goes all the way through the array from beginning to end on every iteration, which means that it keeps pointlessly re-examining (i.e. comparing) all of the elements that have already been sorted, over and over again.

Bear in mind that after the first iteration, the last element is the biggest (and it will remain so thereafter), and after the second iteration ,the next-to-last element is the 2nd biggest (and it will remain so thereafter), and so on. Therefore there is no reason to look at those elements ever again, so you should "shorten" the array from the top down on each succeeding iteration, thus minimizing the number of comparisons.

Like this:
    for (int s=size-1; s>0; s--)
    {
        for (int k=0; k<s; k++)
        {
            if (ar[k] > ar[k+1])
            {
                temp = ar[k];
                ar[k] = ar[k+1];
                ar[k+1]  = temp;
            }
        }
    }



Bubble-sort is inherently an inefficient algorithm, but that's no reason to make it even less efficient.



THhanks a million for pointing this. I am trying this algo because I am a beginner and have tried this algo for the first time.

THanks again!
Was This Post Helpful? 0
  • +
  • -

#6 Munawwar  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 162
  • View blog
  • Posts: 457
  • Joined: 20-January 10

Re: Arrays Bubble sort

Posted 13 January 2011 - 02:51 PM

There are slightly more optimized variations for bubble sort. Like s=0 to s<size-1, k=i to k<size-1.
At each iteration of s, one element "bubbles up" (gets sorted). The inner iteration skips the already sorted elements (and that's why the inner loop starts at k=i) - Here's a visualization of what I mean

This post has been edited by Munawwar: 13 January 2011 - 03:39 PM

Was This Post Helpful? 0
  • +
  • -

#7 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Arrays Bubble sort

Posted 13 January 2011 - 03:17 PM

View PostMunawwar, on 13 January 2011 - 04:51 PM, said:

There are slightly more optimized variations for bubble sort. Like s=0 to s<size-1, k=i to k<size-1.
At each iteration of s, one element "bubbles up" (gets sorted). The inner iteration skips the already sorted elements (and that's why the inner loop starts at k=i)

Not correct. First of all what is i? If you meant s, that wouldn't skip the already-sorted elements, it would skip the unsorted elements at the beginning of the array.

Instead, see post #4.
Was This Post Helpful? 1
  • +
  • -

#8 Munawwar  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 162
  • View blog
  • Posts: 457
  • Joined: 20-January 10

Re: Arrays Bubble sort

Posted 13 January 2011 - 03:32 PM

Yup, I meant k=s. And oops, I screwed up the algorithm. It should loop backwards, from k=size-1 to k>s, and swap array[k] and a[k-1].

EDIT: Just tested it.
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

int main (void)
{
    int a[]={1,9,5,3,2,4,7,0,8,6}, size=10, temp;
    for(int s=0;s<size;s++) {
        for(int k=size-1;k>s;k--) {
            if(a[k-1]>a[k]) {
                temp=a[k-1];
                a[k-1]=a[k];
                a[k]=temp;
            }
        }
    }
    copy(a,a+size,ostream_iterator<int>(cout,"\t"));
    return 0;
}


This post has been edited by Munawwar: 13 January 2011 - 03:39 PM

Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5780
  • View blog
  • Posts: 12,595
  • Joined: 16-October 07

Re: Arrays Bubble sort

Posted 14 January 2011 - 07:13 AM

I HATE FAKE BUBBLE SORTS! Sorry, it's a pet peeve.

Quote

The only significant advantage that bubble sort has over most other implementations, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted is efficiently built into the algorithm.

-- http://en.wikipedia....iki/Bubble_sort


That is, the most obvious characteristic of a bubble sort is the use of a flag. No flag, no bubble sort.

Simple bubble sort:
void bubbleSort(int a[], int size) {
	bool flag = true;
	while(flag) {
		flag = false;
		for(int i=0; i<size-1; i++) {
			if(a[i+1]<a[i]) {
				int temp = a[i];
				a[i] = a[i+1];
				a[i+1] = temp;
				flag = true;
			}
		}
	}
}



Knowing that the last value will be in order after one pass, you can speed this up by continuously decrementing the size.
void bubbleSort(int a[], int size) {
	bool flag = true;
	while(flag) {
		flag = false;
		for(int i=0; i<size-1; i++) {
			if(a[i+1]<a[i]) {
				int temp = a[i];
				a[i] = a[i+1];
				a[i+1] = temp;
				flag = true;
			}
		}
		size--;
	}
}



Because the bubble sort always considers it's neighbor, it lends itself to sorting sequential items that aren't arrays, like linked lists. You just take the first, move next and start working. Here's an example of the logic with an array.
void bubbleSort(int *a, int size) {
	const int *tail = a+size;
	bool flag = true;
	while(flag) {
		int *prior = a;
		int *current = prior+1;
		flag = false;
		while(current!=tail) {
			if(*current<*prior) {
				int temp = *current;
				*current = *prior;
				*prior = temp;
				flag = true;
			}
			prior = current;
			current = prior+1;
		}
		tail--;
	}
}



I feel better now. Hope this helps someone.

This post has been edited by baavgai: 14 January 2011 - 07:14 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1