sorts

[ocKiNOsIi]

could someone help me with this portion

// Add 2 sorts of your own. Document which sort you implemented
// <add code> Add your first sort algorithm in here
void bubbleSort(int array[], int size, bool verbose=false) {
  // if verbose is set to true, display (cout) step-by-step progress of sort
  if (verbose) {
    cout << "  "<< BUBBLE_SORT_NAME <<" has not been implemented.\n";  // replace when implemented
    // if no step-by-step progress is displayed when verbose is true, points reduced!
  }
  // doesn't do anything! <add code>
}


// <add code> Add your second sort algorithm in here
void insertionSort(int array[], int size, bool verbose=false) {
  // if verbose is set to true, display (cout) step-by-step progress of sort
  if (verbose) {
    cout << "  "<< INSERTION_SORT_NAME <<" has not been implemented.\n";  // replace when implemented
    // if no step-by-step progress is displayed when verbose is true, points reduced!
  }
  // doesn't do anything! <add code>
}




//==============
// this is what I found in another code but the verbose part is confusing me

void insertionSort(int array[], int size) {
int startScan, key, index;
for (startScan = 1; startScan < size; startScan++) {
key = array[startScan];
index = startScan - 1;
/* Move elements of array[0..(startScan - 1)], that are
greater than key, to one position ahead
of their current position */
while (index >= 0 && array[index] > key) {
array[index + 1] = array[index];
index = index - 1;
}
array[index + 1] = key;
}
}

//

void bubbleSort(int array[], int size) {
for (int startScan = 0; startScan < (size - 1); startScan++) {
for (int index = startScan + 1; index < size; index++) {
if (array[index] < array[startScan]) {
int temp = array[startScan];
array[startScan] = array[index];
array[index] = temp;
}
}
}
}

[salem c]

"Finding" code has rotted your brain to the point you can only manage copy/paste.

void insertionSort(int array[], int size, bool verbose=false) {
  // if verbose is set to true, display (cout) step-by-step progress of sort
  if (verbose) {
    cout << "  "<< INSERTION_SORT_NAME <<" has not been implemented.\n";  // replace when implemented
    // if no step-by-step progress is displayed when verbose is true, points reduced!
  }
  // doesn't do anything! <add code>

  // well now it does something!
int startScan, key, index;
for (startScan = 1; startScan < size; startScan++) {
key = array[startScan];
index = startScan - 1;
/* Move elements of array[0..(startScan - 1)], that are
greater than key, to one position ahead
of their current position */
while (index >= 0 && array[index] > key) {
array[index + 1] = array[index];
index = index - 1;
}
array[index + 1] = key;
}


}

I could have indented it properly, but since you're too lazy to manage that much, I left it as it was.

[George P]

Are you required to manually code a sort algorithm? The C++ std::sort in <algorithm> is a lot less painful and prone to "I'm just a noob" boo-boos.

std::sort works with all the C++ containers, including regular arrays.
https://en.cppreference.com/w/cpp/algorithm/sort

Is that code something you wrote, or something you "found?" Bits and pieces. The comments are a good indicator it is the latter.

It doesn't include <cstdlib/stdlib.h>, yet it uses srand/rand. It has <random>, allegedly for "DevC++" but it never uses the C++ random features.

This looks like a very stitched up pile of Frankenstein code.

[jonnin]

oo oo I get to post my sort :) Much, much faster than the ones you found on the internet, as you can see with the million ints. I really need to re-do it, its still all 1995 though I did splice in a vector instead of array.

void ssort(vector<int> &list)
{
	size_t size = list.size();
	int temp;
	size_t i, j, dx=0;		
	size_t harr[] = 
	{ 
	    0, /*terminal condition for sort	*/ 		
		
1,
10,
53,
105,
542,
1047,
6239,
16256,
56720,
134096,
579823,
1000000,
5430201,
999999999 /*terminal condition for find index		*/
	};	

	while(size/2 > harr[++dx]); /*get index in sequence, +1   */
	
	for(dx--;dx;dx--)  /*while not 0 in sequence*/
	{
     const  size_t hdx = harr[dx]; /*saves some access time! C ok?! */
		for( i = hdx, temp = list[i]; i< size; temp = list[++i])		
		{
			for(j = i; (j >= hdx) && (list[j-hdx] > temp); 
			list[j] = list[j-hdx], j -= hdx);		
			list[j] = temp; 
		}			
	}
}



int main()
{
  vector<int> v(1000000);
  std::default_random_engine generator;
  std::uniform_int_distribution<int> distribution(-10000,10000);
    for (int i=0; i<v.size(); ++i) 
	{
     v[i] = distribution(generator);
	}

    auto start = chrono::high_resolution_clock::now();
	ssort(v);
	auto end = chrono::high_resolution_clock::now();
	cout << 1.0e-6*(chrono::duration_cast<chrono::microseconds>(end - start).count()) << " seconds\n";
}

0.068184 seconds

[ocKiNOsIi]

its working code that I had to add to. I separated what I had and what I found online that was related

[jonnin]

fair enough, but at some point you may like to check out something that isnt N*N. The brute force sorting family are boring and slow. Even though c++ has a strong sort, not every language does and the algorithms can help you think about other problems and how to do things smarter. Its only 26-37 really, 10 lines of code, exponentially faster..

[Duthomhas]

As this is clearly a homework, I’m gonna spout some unwanted (and un-asked-for) advice:

Life is a whole lot easier and less confusing if you just take the time to understand the algorithm yourself.

Splicing together random example stuff off the internet makes you spend more time and mental energy on a problem than you ever would have if you just did it yourself to begin with.


Insertion Sort:
  ① Get next unsorted element
  ② Sort that element with respect to the previous element (swap if necessary)
  ③   Repeat until no swaps are necessary — element is now in its final position
  ④ Repeat until there are no unsorted elements


Bubble Sort:
  ① For each element in the array:
  ②   Sort it with respect to the next element (swap if necessary)
  ③ Repeat until no swaps were made


Both of these sorts require very minimal brainpower and work very simply. The only thing you must be careful with is not exceeding the array bounds.

Looking at them, you should also realize that Bubble Sort and Insertion Sort are very similar, they use the same basic operation to sort themselves. The main difference is that Insertion Sort works backwards with a single element until that element is sorted, while the Bubble Sort pays no attention to any of that and just keeps making passes over the entire array until no swaps were made. Do you see why Insertion Sort is a better algorithm?