Array Sorting?

[faieq92]

for(int j=2;j<10;j++)
{
int key = heights[j];//so key is 2?
int i = j-1;//i is 1?

while(i>0 && heights[i] > key)
{heights[i+1]=heights[i];
i=i-1;}
heights[i+1] = key;
}

can someone explain this bit of code to me?

im finding it hard to reply to the posttoo?

[firedraco]

What parts exactly are you having trouble understanding?

[Raezzor]

No, key equals the value contained in the element located at height[j]. First time through, that element is actually height[2], 2nd time through it's height[3] etc.

As for i, yes, the first time through the loop i = 1, second time i = 2, etc.

[faieq92]

I don't understand what it should be used for?

[partytime4321]

for(int j=2;j<10;j++)
{
int key = heights[j]; //so key is 2? (no, 2 is the starting index of the for loop... what this means is you have an array with the sort starting at heights[2] and going untill heights [9] (less then 10))

int i = j-1;//i is 1? // yes, initally it is one, but as the loop progresses it will i will count from 1 to 8, always being one less then j

while(i>0 && heights[i] > key)
{
heights[i+1]=heights[i];
i=i-1;
}
heights[i+1] = key;
}

I tried to understand the while loop part but i had difficulties... This appears to be something called a Bubble sort, or similar (if i am not mistaken, Im still new too)... Here is what i think is a similar but easier algorithm...

int heights[50];
//init heights to something random

bool swapped;
do {
swapped = false;

for (int i = 0; i <49; i++)
{
if (heights[i] < heights [i + 1])
{
swapped = true;
int temp = heights[i+1]; // temporary holder for variables during the swap, some algorithms dont need this but its easier to explain
heights [i+1] = heights [i];
heights[i] = temp;
}
}while (swapped == true); // if no changes are made, the array is sorted and thus we are done 

This should work, it is bubblesort which is simple but slow... computation speed increases exponentially with the size of the data (assuming it is not already in order, if it is its fast)

[partytime4321]

You can change the size of the array as long as the for loop is one less then it

[faieq92]

thank you but what is the use of key then?

[Darkmaster]

sorting an array is that simple:

#include<algorithm>

int main()
{
   int A[10] = {1,2,3,4,5,6,7,8,9,10};
   std::sort(A, &A[10]);
}

[Adijunn]

without using the <algorithm> library, you can sort a set of numbers like this:


#include <iostream>

using namespace std;

void spot(int& a, int& b)
{
int temp;
temp = a;
a = b;
b = temp;
}

int main(int argc, const char * argv[])
{

int a[5];
for(int i=0; i<5; i++)
{
cin>>a[i];

}


int s = 0;

do {
s=0;
for(int x=0; x<4; x++)
{
if(a[x]>a[x+1])
{
spot(a[x], a[x+1]);
s++;
}
}

}while(s!=0);

cout<<"\n";

for(int b=0; b<5; b++)
{
cout<<a[b]<<"\n";
}

return 0;
}

[faieq92]

so what is key in my code meant to be used for . can anyone give me an example using my bit of code?

[faieq92]

INSERTION-SORT(A)

for j = 2 to length[A]

key = A[j]

i = j - 1

while i > 0 and A[i] > key

A[i+1] = A[i]

i = i - 1
A[i+1] = key

[faieq92]

that's the psuedocode that I used to create my code? and this was the brief

Implement the following pseudocode using your designated language. In particular, observe that this is a procedure taking an array as input (you must also pass the length of the array as a parameter for C++). Remember the things to watch for - such as the difference in indexing between pseudocode and real code!

have I done it correctly then ? I still don't understand what the pseudo code is meant to do it says it takes an array as an input??


input for what?

[faieq92]

ok ive been re reading this thread 100 times where is the swap feature in my code?

Sorry if im asking too many questions but I really need to understand this as its the basics for my course