Array sorting problem

littleshrimp

Array sorting problem [Copy link]

 

There is an array uint8_t buf[] = {7,8,9,1,2,3,4,5,6};

There is no need to judge the values stored in the array. If only one variable "uint8_t tmp" is allowed, how can I quickly set buf to {1, 2, 3, 4, 5, 6, 7, 8, 9}?

dcexpert

Bubble sort?

littleshrimp

dcexpert published on 2020-12-24 22:14 Bubble sort?

This is equivalent to shifting 123456 to the left three times, and then adding 789 to the end of 6. It would be very convenient to create another array, but if the array is very long and the memory is limited, how to process the array quickly is a problem.

littleshrimp

dcexpert published on 2020-12-24 22:14 Bubble sort?

This is different from bubbling because you don't need to consider the contents of the array. You just move the data after the specified index to the front and then add the data before the index to the back.

shipeng

Can it be like this: define it a little larger uint8_t buf[] = {7,8,9,1,2,3,4,5,6,0,0,0}; then define a pointer to point to uint8_t *ptr=&buf[3]; each time sorting, just move the content of 789 to the end, so that ptr[] can be used as the sorted array.

dcexpert

littleshrimp published on 2020-12-24 23:35 It is equivalent to shifting 123456 to the left three times, and then adding 789 to the end of 6. It would be convenient to create another array, but if the array is very long and the memory is limited...

Isn't it still similar to bubble sort? It is slightly less efficient, but simple and takes up less memory.

huo_hu

The sorting algorithm is related to the characteristics of the data. Since your data is too small, it is difficult to say what the characteristics are.

I remember that heap sort is the fastest in basically ordered situations, but I don't remember it clearly.

huo_hu

The efficiency issue must be combined with the actual situation. For example, each piece of data corresponds to a file on the disk, and it takes a lot of time to move a file. At this time, it is very important to minimize the number of moves.

damiaa

选择排序慢了点

//冒泡法快点

lcofjp

This is a homework question in a data structure book.

Step 1: Reverse the order of 7-9

Step 2: Reverse the order of 1-6

Step 3: Flip the entire array

littleshrimp

The position of each data in the data must be moved, and the minimum number of moves is buf_len + 1 times

I can think of moving data in the following way

But I have no idea how to write the code yet

w494143467

This is a question worth thinking about. Write it down in a small notebook first. You may come up with some good ideas.

viphotman

Use y= x+4 [0 ,5] ; y=x-6 [6,9] to convert the coordinates of buf[y];

littleshrimp

lcofjp posted on 2020-12-25 11:18 This is a homework question in a data structure book. Step 1: Reverse the order of 7-9. Step 2: Reverse the order of 1-6. Step 3: Reverse the whole...

This approach can be done, but it requires many steps.

ljh10051

Sorting is too simple. Usually, questions about circular ordered arrays test binary search.

kirk

uint8_t buf[] = {7,8,9,1,2,3,4,5,6};

#define change(src, a, b) if((a) > (b)){(src) = (a); (a) = (b); (b) = (src);}
void main()
{
uint8_t tmp;
change(tmp, buf[0], buf[1]);
change(tmp, buf[0], buf[2]);
change(tmp, buf[0], buf[3]);
change(tmp, buf[0], buf[4]);
change(tmp, buf[0], buf[5]);
change(tmp, buf[0], buf[6]);
change(tmp, buf[0], buf[7]);
change(tmp, buf[0], buf[8]);

change(tmp, buf[1], buf[2]);
change(tmp, buf[1], buf[3]);
change(tmp, buf[1], buf[4]);
change(tmp, buf[1], buf[5]);
change(tmp, buf[1], buf[6]);
change(tmp, buf[1], buf[7]);
change(tmp, buf[1], buf[8]);

change(tmp, buf[2], buf[3]);
change(tmp, buf[2], buf[4]);
change(tmp, buf[2], buf[5]);
change(tmp, buf[2], buf[6]);
change(tmp, buf[2], buf[7]);
change(tmp, buf[2], buf[8]);

change(tmp, buf[3], buf[4]);
change(tmp, buf[3], buf[5]);
change(tmp, buf[3], buf[6]);
change(tmp, buf[3], buf[7]);
change(tmp, buf[3], buf[8]);

change(tmp, buf[4], buf[5]);
change(tmp, buf[4], buf[6]);
change(tmp, buf[4], buf[7]);
change(tmp, buf[4], buf[8]);

change(tmp, buf[5], buf[6]);
change(tmp, buf[5], buf[7]);
change(tmp, buf[5], buf[8]);

change(tmp, buf[6], buf[7]);
change(tmp, buf[6], buf[8]);

change(tmp, buf[7], buf[8]);
}

kirk

In fact, if you consider the size, tmp can be omitted