Bubble Sort / selection problem

This is a discussion on Bubble Sort / selection problem within the C++ Programming forums, part of the General Programming Boards category; Supose you have a group of N numbers and would like to determine the kth largest. One way to solve ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    Bubble Sort / selection problem

    Supose you have a group of N numbers and would like to determine the kth largest.
    One way to solve this problem would to read N numbers into an array, sort them in
    decreasing order by some simple algorithm such as bubblesort, and then return the
    element in position.
    Here is what the problem is asking for
    Write a program to solve this problem. Let k = N/2. Draw a table showing the running time of your program for various values of N.
    Can some one get me started on the code for this problem or explain it better to me.
    Input file: 300 5000 300000 200000 30 45 70 500000 3000


    Code:
    #include< iostream >
    #include< fstream >
    
    
    const int MAXVALUES = 9;
    using namespace std;
    
    int main()
    {
        
    
    
        //Declare the streams and the input and output files
    	ifstream inFile;
        ofstream outFile;
    
    	inFile.open("A:/input1.txt");
        outFile.open("A:/output1.txt");
    
    
        int i = 0;
    	int j = 0;
    	int temp = 0;
    	int sortValue[MAXVALUES];
    
    	
    	for(i=0; i<MAXVALUES; i++)
    	{
    inFile>> sortValue[i];
    
    	}
    
    	inFile.close();
    for(i=0;i<MAXVALUES-1;++i)
    	{
    		for(j=0;j<MAXVALUES-1;j++)
    		{
    			if(sortValue[j+1] > sortValue[j])
    			{
    				temp = sortValue[j];
    				sortValue[j] = sortValue[j+1];
    				sortValue[j+1] = temp;
    			}
    		}
    	}
    
    	for(i=0;i<MAXVALUES;i++)
    	outFile<< "Array[" << i << "] : " << sortValue[i] << endl;
    
    
    
    
    return 0;
    }
    Last edited by Drew; 08-25-2003 at 06:46 PM.

  2. #2
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Sounds to me like you would want to divide the number of elements in the array by two and then display that element, ie:
    Code:
    int array[N]=//some values
    //if the number of elements is known
    int elemCnt = (N/2); //N/2=k
    //sort the elements
    ...
    //output the kth highest number
    cout<<array[elemCnt];
    That would be my guess
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    so I would do this

    So in my code I would change this line int sortValue[MAXVALUES]
    to this int sortValue[MAXVALUES/2]?

    Code:
    #include< iostream >
    #include< fstream >
    
    
    const int MAXVALUES = 9;
    using namespace std;
    
    int main()
    {
        
    
    
        //Declare the streams and the input and output files
    	ifstream inFile;
        ofstream outFile;
    
    	inFile.open("A:/input1.txt");
        outFile.open("A:/output1.txt");
    
    
        int i = 0;
    	int j = 0;
    	int temp = 0;
    	int sortValue[MAXVALUES/2];
    
    	
    	for(i=0; i<MAXVALUES; i++)
    	{
    inFile>> sortValue[i];
    
    	}
    
    	inFile.close();
    for(i=0;i<MAXVALUES-1;++i)
    	{
    		for(j=0;j<MAXVALUES-1;j++)
    		{
    			if(sortValue[j+1] > sortValue[j])
    			{
    				temp = sortValue[j];
    				sortValue[j] = sortValue[j+1];
    				sortValue[j+1] = temp;
    			}
    		}
    	}
    
    	for(i=0;i<MAXVALUES;i++)
    	outFile<< "Array[" << i << "] : " << sortValue[i] << endl;
    
    
    
    
    return 0;
    }

  4. #4
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    No that crashes

    No that crashes

  5. #5
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Supose you have a group of N numbers and would like to determine the kth largest.
    I just meant that after you sorted all the elements, you could output sortValue[N/2], but im not sure what's meant by:
    Draw a table showing the running time of your program for various values of N.
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  6. #6
    Wen Resu
    Join Date
    May 2003
    Posts
    219
    this is an Assigment, thats propably written work showing what happens within the code.
    first
    int sortValue[MAXVALUES/2];
    your setting an array, arrays have to know how big they will be at compile time(unlesss you wana learn how to do dynmic memory allocation>
    k = 4.5th item, choose how you wana round it :P
    yours sorting your elements. so the 4th largest number in a 9 number array would be you 6th number <assuming your sort least->greatest>
    your program works fine. cept your head should be set up
    #include <iostream>
    rather then
    #include< iostream >
    anyway your program outputs correctly sorted things to file
    you have an array all you need now is know which pay of the array you should output

    For the write a table to show running times for n, i'm assuming that means show how the program is effect as the number of well numbers it must process grows larger.

  7. #7
    Grammar Police HybridM's Avatar
    Join Date
    Jan 2003
    Posts
    355
    when you say "rather then" you mean "rather than", you may say I'm anal, but this is one of the things that annoys the hell out of me. If it was a typo then apologies but FAR too many people on FAR too many forums do it, futuremark is one of the worst.

    Incase you're wondering the other thing that annoys me is "m8" and other such "8" abbreviations.

    EDIT: This is the part where I usually get ripped apart over my own spelling and grammar. I know it's not perfect, I never said it was.
    Last edited by HybridM; 08-26-2003 at 05:18 AM.
    Thor's self help tip:
    Maybe a neighbor is tossing leaf clippings on your lawn, looking at your woman, or harboring desires regarding your longboat. You enslave his children, set his house on fire. He shall not bother you again.

    OS: Windows XP
    Compiler: MSVC

  8. #8
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    Instead of using ifstream and ofstream, use a fstream and open with the ios::in and ios:ut properties.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. testing a bubble sort algorithm
    By rushhour in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2009, 01:00 AM
  2. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 05:48 AM
  3. Array/Structure Bubble Sort
    By JKI in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2003, 12:59 PM
  4. Selection sort problem
    By kippwinger in forum C++ Programming
    Replies: 1
    Last Post: 07-03-2003, 02:35 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21