Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.02.2010, 21:42
ZeniXoid

 
Сообщений: n/a

Помогите плз с сортировкой вставками.
"Сортировка вставками, место помещения очередного элемента в отсортированную часть производить с помощью двоичного поиска. Двоичный поиск оформить в виде отдельной функции."

Я знаю что такое двоичный поиск и сортировка вставками, но немогу логически связать это и написать код на Си, долго парюсь, голова трещит'
  #2  
Старый 04.02.2010, 22:47
ZeniXoid

 
Сообщений: n/a

//Вот мои безуспешные старания
#include <stdio.h>
#include <string.h>
#define N 100
void enter_str(char * str);
int binary_search(char *items, int count, char key, int start);
int main()
{
char items[N];
char t;
int count,key,n=0;
int i,j;
printf("Enter string:");
enter_str(items);
count=strlen(items);
for(i=1;i<count;i++)
{
if(items[i-1]>items[i])
{
key=binary_search(items,i,items[i],0);
t=items[i];
for(j=i;j>key;j-=1)
{
items[j]=items[j-1];
}
items[key]=t;
printf("%d:\t%s\n",i,items);
}

}
printf("\nSorted items: %s\n",items);
return 0;
}
void enter_str(char * str)
{
int i;
for(i=0;str[i-1]!='\n';i+=1)scanf("%c",&str[i]);
str[i-1]=0;
}
int binary_search(char *items, int count, char key, int start=0)
{
int low, high, mid;
low=start;
high=--count;
while(low<=high)
{
mid=(low+high)/2;
if(key < items[mid])
{
high=mid-1;
if(high==low)return mid;
}
else if(key > items[mid])
{
low=mid+1;
if(high==low)return mid;
}
else return mid; /* ключ найден */
}
return mid;
}
/*Результат работы
Enter string:84452347464245886433234
1: 48452347464245886433234
2: 44852347464245886433234
3: 45482347464245886433234
4: 42548347464245886433234
5: 34254847464245886433234
6: 34254487464245886433234
7: 34254748464245886433234
8: 34425474864245886433234
9: 34425467484245886433234
10: 34442546748245886433234
11: 23444254674845886433234
12: 23444245467485886433234
13: 23444245546748886433234
16: 23444245564674888433234
17: 23444424556467488833234
18: 23344442455646748883234
19: 23334444245564674888234
20: 22333444424556467488834
21: 22333344442455646748884
22: 22333344442445564674888

Sorted items: 22333344442445564674888
*/
  #3  
Старый 05.02.2010, 14:39
ZeniXoid

 
Сообщений: n/a

/*Вообщем я был не вдухе... на следующий день спокойно все обдумал, переделал код и все получилось, незнаю может кто и предложет более лучший код, но приведу свой вариант здесь, т.к. не зря всетки я здесь писал хоть и не кто не ответил за столь короткий срок...
*/
#include <stdio.h>
#include <string.h>
#define N 100
void enter_str(char * str);
int binary_search(char *items, int count, char key);
int main()
{
char items[N];
char t;
int count,k;
register int i,j;
puts("Welcome to my lab No4!!!");
printf("Enter string:");
enter_str(items);
count=strlen(items);
if(items[0]>items[1])
{
t=items[0];
items[0]=items[1];
items[1]=t;
}
for(i=2;i<count;i++)
{
k=binary_search(items,i,items[i]);
t=items[i];
for(j=i;j>k;j-=1)
{
items[j]=items[j-1];
}
items[k]=t;
printf("%d:\t%s\n",i,items);

}
printf("\nSorted items: %s\n",items);
return 0;
}
void enter_str(char * str)
{
int i;
for(i=0;str[i-1]!='\n';i+=1)scanf("%c",&str[i]);
str[i-1]=0;
}
int binary_search(char *items, int count, char key)
{
int low, high, mid;
low=0;
high=count-1;
if(items[count]>=items[high])return count;
else
while(low<=high)
{
mid=(low+high)/2;
if(key < items[mid])
{
high=mid-1;
if(high==mid)return mid;
}
else if(key > items[mid])
{
low=mid+1;
if(mid==high)return mid+1;
}
else return mid; /* ключ найден */
}
return mid;
}
  #4  
Старый 05.02.2010, 14:41
ZeniXoid

 
Сообщений: n/a

на этот раз результат таков:
Enter string:84452347464245886433234
2: 44852347464245886433234
3: 44582347464245886433234
4: 24458347464245886433234
5: 23445847464245886433234
6: 23444587464245886433234
7: 23444578464245886433234
8: 23444457864245886433234
9: 23444456784245886433234
10: 23444445678245886433234
11: 22344444567845886433234
12: 22344444456785886433234
13: 22344444455678886433234
14: 22344444455678886433234
15: 22344444455678886433234
16: 22344444455667888433234
17: 22344444445566788833234
18: 22334444444556678883234
19: 22333444444455667888234
20: 22233344444445566788834
21: 22233334444444556678884
22: 22233334444444455667888

Sorted items: 22233334444444455667888
  #5  
Старый 05.02.2010, 15:22
ZeniXoid

 
Сообщений: n/a

//убрал лишнее..
#include <stdio.h>
#include <string.h>
#define N 100
void enter_str(char * str);
int binary_search(char *items, int count, char key);
int main()
{
char items[N];
char t;
int count,k;
int i,j,n=0;
printf("Enter string:\n");
enter_str(items);
count=strlen(items);
for(i=1;i<count;i++)
{
k=binary_search(items,i,items[i]);
t=items[i];
for(j=i;j>k;j-=1)
{
items[j]=items[j-1];
}
items[k]=t;
n+=1;
printf("\n%s <- %d",items,n);

}
printf(" (sorted items)\n");
return 0;
}
void enter_str(char * str)
{
int i;
for(i=0;str[i-1]!='\n';i+=1)scanf("%c",&str[i]);
str[i-1]=0;
}
int binary_search(char *items, int count, char key)
{
int low, high, mid;
low=0;
high=count-1;
if(items[count]>=items[high])return count;
else
while(low<=high)
{
mid=(low+high)/2;
if(key < items[mid])
{
high=mid-1;
if(high==mid)return mid;
}
else if(key > items[mid])
{
low=mid+1;
if(mid==high)return mid+1;
}
else return mid; /* ключ найден */
}
return mid;
}
  #6  
Старый 30.05.2010, 14:07
Hippi

 
Сообщений: n/a

спасибо)) помогли!
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
сортировка вставками с двоичным поиском незарегистрированный Сортировка и поиск 4 05.02.2010 14:44
помогите разобраться с сортировкой lavan Сортировка и поиск 2 20.03.2009 19:48
задача с быстрой сортировкой гость Сортировка и поиск 2 16.11.2008 21:09