Keep track of a single element after sorting an array

[litoscu]

I have an array of number in which one element is "activeItem" determined by the position in the array. After I sort it, that "activeItem" will most likely change locations, I need to keep it as "activeItem" in the new location. Here's what I mean:

-5 16 [8] 9 -12 0 -3 <== Unsorted
-12 -5 -3 0 [8] 9 16 <== Expected result
-12 -5 [-3] 0 8 9 16 <== What I'm getting

"activeItem" stays in a[2] and it should go to a[4] any ideas of how to go about this? Here's what I have for the sorting functions. Haven't passed "activeItem" because I don't know which one should get it.

  void sort(int a[], int numberUsed)
{
	int indexOfNextSmallest;
	for(int index=0; index<numberUsed-1; index++)
	{
		indexOfNextSmallest=indexOfSmallest(a, index, numberUsed);
		swapValues(a[index], a[indexOfNextSmallest]);
	}
}

void swapValues(int& v1, int& v2)
{
	int temp;
	temp = v1;
	v1 = v2;
	v2 = temp;
}

int indexOfSmallest(const int a[], int startIndex, int numberUsed)
{
	int min = a[startIndex], indexOfMin = startIndex;
	for(int index=startIndex+1; index<numberUsed; index++)
		if(a[index] < min)
		{
			min = a[index];
			indexOfMin = index;
		}
		return indexOfMin;
}

[cire]

The simplest thing would be to (do a binary) search for the item after the array is sorted.

[litoscu]

Thank you for the reply. Is there a way to do this without using vectors? Or is that the only/best way to solve this? I would ideally like to use functions, variables and the array to get it done. Thank you.

[JLBorges]

#include <iostream>
#include <algorithm>
#include <functional>

void print( const int a[], std::size_t n, std::size_t position_of_active_item )
{
   std::cout << "{ " ;
   for( std::size_t i = 0 ; i < n ; ++i )
       if( i == position_of_active_item ) std::cout << '[' << a[i] << "] " ;
       else std::cout << a[i] << ' ' ;
   std::cout << "}\n" ;
}


int main()
{
    int a[] = { -5, 16, 8, 9, -12, 0, -3 } ;
    constexpr std::size_t N = sizeof(a) / sizeof(*a) ;
    std::size_t position_of_active_item = 2 ;
    print( a, N, position_of_active_item ) ;

    // swap active item with the first element
    std::swap( a[0], a[position_of_active_item] ) ;
    position_of_active_item = 0 ;

    // sort from the second item onwards
    std::sort( a+1, a+N ) ;
    print( a, N, position_of_active_item ) ;

    // bring the active item into place
    std::size_t i = 1 ;
    for( ; a[i] < a[i-1] && i < N ; ++i ) std::swap( a[i], a[i-1] ) ;
    position_of_active_item = i-1 ;
    print( a, N, position_of_active_item ) ;
}

http://ideone.com/zA4CAl

[nedo]

you could add a third and forth argument to your sort function that will hold the activ items position and value if you have to swap the values you check if any of them is the activ item if it is increment or decrement the position counter.

[litoscu]

JLBorges - Thank you for the code, I can see how you are managing to get the answer. Unfortunately I can't use that *a.

nedo - In making the two extra variables I have a question. I already have a variable that I'm passing by reference to track "activeItem" would I need to do the same to the extra variable? When I run my program the thing that changes is the array position and I need to update that value from one to the next.

I don't think I can submit .exe files in here do I...?

[giblit]

no but you can copy/paste the output from the console ( if by windows click on the symbol in top left corner looks like a grey rectangle , then click edit - > select all then hit the enter key ) or you can output to a text file then copy/paste that. After doing that you can either a under your code put
--- ouput[/code] or use the output tags [output][/output]

Examples:

[code]
//stuff
---
I am an output message![/code]

which looks like

//stuff

I am an output message!

or you can do this
[output]I am an output message![/output]

which looks like this

I am an output message!

[vlad from moscow]

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
	const size_t N = 7;
	int a[N] = { -5, 16, 8, 9, -12, 0, -3 };

		
	for ( int x : a ) std::cout << x << ' ';
	std::cout << std::endl;

	int *active = &a[2];

	std::cout << "The active element is " << *active << " at position " << active - a << std::endl;

	struct Sort
	{
		int * operator ()( int *first, int *last, int *active ) const
		{
			for ( ; first != last; ++first )
			{
				int *min = std::min_element( std::next( first ), last );
				if ( min != last && *min < *first )
				{
					std::iter_swap( first, min );
					if ( first == active ) active = min;
					else if ( min == active ) active = first;
				}
			}

			return ( active );
		}
	};

	active = Sort()( a, a + N, active );

	for ( int x : a ) std::cout << x << ' ';
	std::cout << std::endl;

	std::cout << "The active element is " << *active << " at position " << active - a << std::endl;
	std::cout << std::endl;
}

The output is

-5 16 8 9 -12 0 -3
The active element is 8 at position 2
-12 -5 -3 0 8 9 16
The active element is 8 at position 4

[litoscu]

These are all I'm allowed to use:
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <conio.h>

1. Insert "Insert" key
2. Delete "Delete" key
3. Sort "F2" key
4. Select "Down Arrow" key
5. Move Right "Right Arrow" key
6. Move Left "Left Arrow" key
7. Exit "F1" key

65 10 -3 1 [-15]

Active Item: 4

1. Insert "Insert" key
2. Delete "Delete" key
3. Sort "F2" key
4. Select "Down Arrow" key
5. Move Right "Right Arrow" key
6. Move Left "Left Arrow" key
7. Exit "F1" key

-15 -3 1 10 [65]

Active Item: 4

[JLBorges]

> I can see how you are managing to get the answer. Unfortunately I can't use that
> These are all I'm allowed to use:


Just write your own swap() and sort()
And you don't need anything more than #include <iostream>

#include <iostream>

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

void sort( int a[], std::size_t n )
{
    for( std::size_t i = 0 ; i < n ; ++i )
        for( std::size_t j = i+1 ; j < n ; ++j )
            if( a[j] < a[i] ) swap( a[j], a[i] ) ;
}

void print( const int a[], std::size_t n, std::size_t pos_acive )
{
   std::cout << "{ " ;
   for( std::size_t i = 0 ; i < n ; ++i )
       if( i == pos_acive ) std::cout << '[' << a[i] << "] " ;
       else std::cout << a[i] << ' ' ;
    std::cout << "}\n\nActive Item: " << pos_acive << "\n\n\n" ;
}


int main()
{
    int a[] = { -5, 16, 8, 9, -12, 0, -3, 65, 10, -3, 1 } ;
    const std::size_t N = sizeof(a) / sizeof(*a) ;
    std::size_t pos_acive = 2 ;
    print( a, N, pos_acive ) ;

    ::swap( a[0], a[pos_acive] ) ; // swap active item with the first element
    ::sort( a+1, N-1 ) ; // sort from the second item onwards
    // bring the active item into place
    std::size_t i = 1 ;
    for( ; a[i] < a[i-1] && i < N ; ++i ) std::swap( a[i], a[i-1] ) ;
    pos_acive = i-1 ;

    ::print( a, N, pos_acive ) ;
}

http://ideone.com/HHQRTc

[litoscu]

Thank you all, I will work on it and get back to you later on.

[vlad from moscow]

@JLBorges

What about if the array contains equal elements?

[litoscu]

If that's the case, then they will be sorted according to where in the array the elements are found and the "activeItem" selection will stay on the selected element. I have a completed .exe that shows all the stuff that I need to do, that's where I tested this. I need to come up with code to replicate the functionality of this exe

[dunnmifflsys]

Just in case you need it, here's a way to find the item.

int b = a[/*item you want*/];
int c;
for (int i =0; a[i]!=0;i++ {
if (b==a[i]) {
c = a[i];
}
}

This should find the number after you sort it.

[litoscu]

dunnmifflsys I created a brand new function and called it after my original sort and it didn't do the trick. It's behaving just as if it wasn't there at all.

[litoscu]

Thank you to everyone for your help, I really appreciate it. I finally got the program to do everything that it was supposed to do.